oj.uz

Submission #244569

# Submission time Handle Problem Language Result Execution time Memory
244569 2020-07-04T09:54:08 Z oolimry Potemkin cycle (CEOI15_indcyc) C++14
30 / 100
 1000 ms 2552 KB 
//HAPPY BIRTHDAY!!!
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;

int depth[1005];
vector<int> adj[1005];
vector<int> paths[1005];
vector<ii> backs;
void dfs(int u){
	for(int v : adj[u]){
		if(depth[v] != 0){
			if(depth[v] < depth[u]-1){ ///back edge
				int dist = depth[u] - depth[v];
				backs.push_back(ii(dist, u));
			}
		}
		else{
			depth[v] = depth[u] + 1;
			paths[v].push_back(u);
			dfs(v);
		}
	}
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n, m; cin >> n >> m;
	
	
	if(n <= 10){
		set<ii> edges;
		for(int i = 0;i < m;i++){
			int a, b; cin >> a >> b;
			edges.insert(ii(a,b));
			edges.insert(ii(b,a));
		}
		
		vector<int> v;
		for(int i = 1;i <= n;i++) v.push_back(i);
		
		do{
			
			for(int sz = 4;sz <= n;sz++){
				int can = true;
				for(int i = 0;i < sz;i++){
					int a = v[i];
					int b = v[(i+1)%sz];
					
					if(edges.find(ii(a,b)) == edges.end()){
						can = false;
						break;
					}
				}
				
				int cnt = 0;
				for(int i = 0;i < sz;i++){
					for(int j = 0;j < sz;j++){
						int a = v[i];
						int b = v[j];
						if(edges.find(ii(a,b)) != edges.end()) cnt++;
					}
				}
				
				if(cnt == 2*sz && can){
					for(int i = 0;i < sz;i++) cout << v[i] << " ";
					return 0;
				}
			}
		} while(next_permutation(v.begin(),v.end()));
		
		cout << "no";
		return 0;
	}
	
	for(int i = 0;i < m;i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	for(int i = 1;i <= n;i++){
		if(depth[i] != 0) continue; ///visited;
		backs.clear();
		
		depth[i] = 1;
		dfs(i);
		
		sort(backs.begin(), backs.end());
		for(ii e : backs){
			//cout << e.first << " " << e.second << ":" << endl;
			int u = e.second;
			int targetDepth = depth[u] - e.first;
			//cout << targetDepth << "\n";
			
			vector<int> P;
			while(depth[u] != targetDepth){
				P.push_back(u);
				
				for(int i = (int) (paths[u].size()-1);i >= 0;i--){
					int v = paths[u][i];
					//cout << u << " " << v << endl;
					
					if(depth[v] >= targetDepth){
						u = v;
						break;
					}
				}
			}
			
			P.push_back(u);
			
			if((int) P.size() >= 3){
				for(int x : P) cout << x << " ";
				return 0;
			}
			else{
				paths[e.second].push_back(u);
			}
		
		}
	}
	
	cout << "no";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 504 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Too short sequence
2 Incorrect 5 ms 384 KB Wrong answer on graph without induced cycle

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Wrong answer on graph without induced cycle
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Too short sequence
2 Incorrect 5 ms 512 KB Wrong answer on graph without induced cycle

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1664 KB Too short sequence
2 Correct 10 ms 1152 KB Too short sequence
3 Incorrect 19 ms 1664 KB Wrong answer on graph without induced cycle
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1028 KB Too short sequence
2 Incorrect 15 ms 1024 KB Wrong answer on graph without induced cycle

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2552 KB Too short sequence
2 Incorrect 31 ms 2552 KB Wrong answer on graph without induced cycle
3 Halted 0 ms 0 KB -