Source code for submission s591

Go to diff to previous submission

#include<iostream>
 
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<math.h>
 
#include<vector>
#include<set>
 
using namespace std;
 
#define FOR(i,a,b) for(int i=a; i<=b; i++)
 
#define PII pair<int, int>
#define MP make_pair
#define PB push_back
 
#define SIZE(s) ((int)(s).size())
 
#define ll long long
 
#define MAX 10047
 
int N, M;
vector<int> G[MAX];
 
int colors[MAX];
int color;
 
void dfs(int v)
{
	colors[v] = color;
	FOR(i,0, SIZE(G[v])-1)
	{
		int u = G[v][i];
		if (colors[u] == 0)
			dfs(u);
	}
}
 
int V[MAX];
 
int st4[MAX];
vector<int> st3[MAX];
 
//skusime medzi dvoma vrcholmi
bool skus(int v1, int v2)
{
//	cout << v1 << " " << v2 << endl;
	set<int> vrchols;
	FOR(i,0, SIZE(G[v1])-1) if (G[v1][i] != v2) vrchols.insert( G[v1][i] );
	FOR(i,0, SIZE(G[v2])-1) if (G[v2][i] != v1) vrchols.insert( G[v2][i] );
	return SIZE(vrchols) >= 4;
}
 
int main()
{
	int a, b;
	while(scanf("%d %d",&N, &M)== 2)
	{
		FOR(i,0,N-1) G[i].clear();
		FOR(i,0,N-1) V[i] = 0;
		while(M--)
		{
			scanf("%d %d",&a,&b);
			a--; b--;
			G[a].PB(b);
			G[b].PB(a);
			V[a]++;
			V[b]++;
		}
 
		color = 0;
		FOR(i,0,N-1) colors[i] = 0;
		FOR(i,0,N-1)
		{
			if (colors[i] == 0)
			{
				color++;
				dfs(i);
			}
		}
 
	//	FOR(i,0,N-1) cout << colors[i] << endl;
 
		bool ok = false;
		FOR(c,1,color)
		{
			st4[c] = 0;
			st3[c].clear();
		}
		FOR(i,0,N-1)
		{
			if (V[i] > 3)
				st4[ colors[i] ]++;
			if (V[i] > 2)
				st3[ colors[i] ].PB(i);
		}
 
		FOR(c,1,color)
		{
			if (st4[c] >= 1) ok = true;
			if (SIZE(st3[c]) > 1)
			{
				FOR(i,0, SIZE( st3[c])-1)
					FOR(j, i+1 , SIZE(st3[c])-1)
					{
						if (skus( st3[c][i], st3[c][j])) ok = true;
					}
			}
		}
 
		if (ok) puts("YES");
		else puts("NO");
	}
	return 0;
}
 
 

Diff to submission s528

--- c5.s528.cteam079.fn.cpp.0.fn.cpp
+++ c5.s591.cteam079.fn.cpp.0.fn.cpp
@@ -7,4 +7,5 @@
 
 #include<vector>
+#include<set>
 
 using namespace std;
@@ -42,5 +43,15 @@
 
 int st4[MAX];
-int st3[MAX];
+vector<int> st3[MAX];
+
+//skusime medzi dvoma vrcholmi
+bool skus(int v1, int v2)
+{
+//      cout << v1 << " " << v2 << endl;
+        set<int> vrchols;
+        FOR(i,0, SIZE(G[v1])-1) if (G[v1][i] != v2) vrchols.insert( G[v1][i] );
+        FOR(i,0, SIZE(G[v2])-1) if (G[v2][i] != v1) vrchols.insert( G[v2][i] );
+        return SIZE(vrchols) >= 4;
+}
 
 int main()
@@ -78,5 +89,5 @@
                 {
                         st4[c] = 0;
-                        st3[c] = 0;                     
+                        st3[c].clear();
                 }
                 FOR(i,0,N-1)
@@ -85,5 +96,5 @@
                                 st4[ colors[i] ]++;
                         if (V[i] > 2)
-                                st3[ colors[i] ]++;
+                                st3[ colors[i] ].PB(i);
                 }
 
@@ -91,5 +102,12 @@
                 {
                         if (st4[c] >= 1) ok = true;
-                        if (st3[c] >= 2) ok = true;
+                        if (SIZE(st3[c]) > 1)
+                        {
+                                FOR(i,0, SIZE( st3[c])-1)
+                                        FOR(j, i+1 , SIZE(st3[c])-1)
+                                        {
+                                                if (skus( st3[c][i], st3[c][j])) ok = true;
+                                        }
+                        }
                 }