Source code for submission s640

Go to diff to previous submission

#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
 
using namespace std;
 
#define DEBUG(x) cout << ">>> " << #x << " : " << x << endl;
#define REP(i,a) for (int i = 0; i < (a); ++i)
#define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for (int i = (a); i >= (b); --i)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
 
typedef long long ll;
 
#define maxN 10005
 
int n,m;
int x,y;
vector<int> edges[maxN];
bool found2;
bool visited[maxN];
bool diff;
bool ok;
 
vector<int> th,paw;
 
void comp(int u){
	if(visited[u]) return;
	visited[u]=true;
	if(edges[u].size()>=4) found2=true;
	if(edges[u].size()==3 && !found2){
		REP(i,th.size()){
			diff = 0;
			REP(j,3){
				if(edges[th[i]][j]==u) continue;
				ok=true;
				REP(k,3){
					if(edges[th[i]][j]==edges[u][k]) ok=false;
				}
				if(ok) diff++;
			}
			if(diff>=2){ found2=true; break; }
		}
		th.push_back(u);
 
	}
	REP(i,edges[u].size()){
		comp(edges[u][i]);
	}
}
 
int main() {
	while(scanf("%d%d",&n,&m)==2){
		REP(i,n) edges[i].clear();
		REP(i,n) visited[i]=false;
		found2=false;
		REP(i,m){
			scanf("%d%d",&x,&y);
			x--; y--;
			edges[x].push_back(y);
			edges[y].push_back(x);
		}
		REP(i,n){
			th.clear();
			comp(i);
		}
		if(found2) printf("YES\n");
		else printf("NO\n");
 
	}
 
	return 0;
}
 

Diff to submission s593

--- c5.s593.cteam010.fn.cpp.0.fn.cpp
+++ c5.s640.cteam010.fn.cpp.0.fn.cpp
@@ -32,6 +32,10 @@
 int x,y;
 vector<int> edges[maxN];
-bool found,found2;
+bool found2;
 bool visited[maxN];
+bool diff;
+bool ok;
+
+vector<int> th,paw;
 
 void comp(int u){
@@ -39,6 +43,20 @@
         visited[u]=true;
         if(edges[u].size()>=4) found2=true;
-        if(edges[u].size()==3 && found) found2=true;
-        if(edges[u].size()==3) found=true;
+        if(edges[u].size()==3 && !found2){
+                REP(i,th.size()){
+                        diff = 0;
+                        REP(j,3){
+                                if(edges[th[i]][j]==u) continue;
+                                ok=true;
+                                REP(k,3){
+                                        if(edges[th[i]][j]==edges[u][k]) ok=false;
+                                }
+                                if(ok) diff++;
+                        }
+                        if(diff>=2){ found2=true; break; }
+                }
+                th.push_back(u);
+
+        }
         REP(i,edges[u].size()){
                 comp(edges[u][i]);
@@ -50,5 +68,5 @@
                 REP(i,n) edges[i].clear();
                 REP(i,n) visited[i]=false;
-                found=found2=false;
+                found2=false;
                 REP(i,m){
                         scanf("%d%d",&x,&y);
@@ -58,5 +76,5 @@
                 }
                 REP(i,n){
-                        found=false;
+                        th.clear();
                         comp(i);
                 }