Source code for submission s742

Go to diff to previous submission

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int N,M;
	while(cin >> N >> M) {
		vector< vector<int> > G(N);
		vector<int> D(N,0);
		for(int i =0; i < M; i++) {
		int a,b;
			cin >> a >> b;
			G[--a].push_back(--b);
			G[b].push_back(a);
			D[a]++, D[b]++;}
		int maxD =0;
		for(int i =0; i < N; i++) maxD =max(maxD,D[i]);
		if(maxD > 3) {cout << "YES\n"; continue;}
		if(maxD < 3) {cout << "NO\n"; continue;}
 
		vector<int> comp(N,-1);
		int c =0;
		queue<int> q;
		for(int k =0; k < N; k++) if(comp[k] == -1) {
			q.push(k);
			comp[k] =c;
			while(!q.empty()) {
				int a =q.front();
				for(int i =0; i < G[a].size(); i++) if(comp[G[a][i]] == -1) {
					comp[G[a][i]] =c;
					q.push(G[a][i]);}
				q.pop();}
			c++;}
		vector< vector<int> > d3(c);
		for(int i =0; i < N; i++) if(D[i] == 3) d3[comp[i]].push_back(i);
 
		bool ok =false;
		for(int k =0; k < c; k++) {
			if(d3[k].size() > 10) {ok =true; break;}
			for(int i =0; i < d3[k].size(); i++) for(int j =i+1; j < d3[k].size(); j++) {
				if(ok) break;
				int com =0, a =d3[k][i], b =d3[k][j];
				for(int l =0; l < 3; l++) for(int m =0; m < 3; m++) if(G[a][l] == G[b][m]) com++;
				bool hr =false;
				for(int l =0; l < 3; l++) if(G[a][l] == b) hr =true;
				if(hr && com == 0) ok =true;
				if(!hr && com <= 1) ok =true;}
			if(ok) break;}
		if(ok) cout << "YES\n";
		else cout << "NO\n";}
	return 0;}
 

Diff to submission s688

--- c5.s688.cteam002.fn.cpp.0.fn.cpp
+++ c5.s742.cteam002.fn.cpp.0.fn.cpp
@@ -7,6 +7,5 @@
                 vector< vector<int> > G(N);
                 vector<int> D(N,0);
-                vector<int> d3;
-                for(int i =0; i < M; i++){
+                for(int i =0; i < M; i++) {
                 int a,b;
                         cin >> a >> b;
@@ -15,7 +14,5 @@
                         D[a]++, D[b]++;}
                 int maxD =0;
-                for(int i =0; i < N; i++) {
-                        if(D[i] == 3) d3.push_back(i);
-                        maxD =max(maxD,D[i]);}
+                for(int i =0; i < N; i++) maxD =max(maxD,D[i]);
                 if(maxD > 3) {cout << "YES\n"; continue;}
                 if(maxD < 3) {cout << "NO\n"; continue;}
@@ -34,13 +31,19 @@
                                 q.pop();}
                         c++;}
+                vector< vector<int> > d3(c);
+                for(int i =0; i < N; i++) if(D[i] == 3) d3[comp[i]].push_back(i);
                 
                 bool ok =false;
-                for(int i =0; i < d3.size(); i++) for(int j =0; j < d3.size(); j++) if(comp[d3[i]] == comp[d3[j]]) {
-                        int com =0, a =d3[i], b =d3[j];
-                        for(int k =0; k < 3; k++) for(int l =0; l < 3; l++) if(G[a][k] == G[b][l]) com++;
-                        bool hr =false;
-                        for(int k =0; k < 3; k++) if(G[a][k] == b) hr =true;
-                        if(hr && com == 0) ok =true;
-                        if(!hr && com <= 1) ok =true;}
+                for(int k =0; k < c; k++) {
+                        if(d3[k].size() > 10) {ok =true; break;}
+                        for(int i =0; i < d3[k].size(); i++) for(int j =i+1; j < d3[k].size(); j++) {
+                                if(ok) break;
+                                int com =0, a =d3[k][i], b =d3[k][j];
+                                for(int l =0; l < 3; l++) for(int m =0; m < 3; m++) if(G[a][l] == G[b][m]) com++;
+                                bool hr =false;
+                                for(int l =0; l < 3; l++) if(G[a][l] == b) hr =true;
+                                if(hr && com == 0) ok =true;
+                                if(!hr && com <= 1) ok =true;}
+                        if(ok) break;}
                 if(ok) cout << "YES\n";
                 else cout << "NO\n";}