oj.uz

Submission #131326

# Submission time Handle Problem Language Result Execution time Memory
131326 2019-07-17T04:27:58 Z gs14004 Potemkin cycle (CEOI15_indcyc) C++17
100 / 100
 51 ms 3208 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
using lint = long long;
using pi = pair<int, int>;

vector<int> gph[MAXN];
int n, m, cnt[MAXN], idx[MAXN];
int mark[MAXN], vis[MAXN], par[MAXN];

void report(int x, int y){
	gph[x].erase(find(gph[x].begin(), gph[x].end(), y));
	gph[y].erase(find(gph[y].begin(), gph[y].end(), x));
	for(int i=1; i<=n; i++){
		if(binary_search(gph[i].begin(), gph[i].end(), x) && 
			binary_search(gph[i].begin(), gph[i].end(), y)){
			mark[i] = 1;
		}
	}
	queue<int> que;
	vis[x] = 1;
	que.push(x);
	while(!que.empty()){
		int x = que.front(); que.pop();
		for(auto &i : gph[x]){
			if(!mark[i] && !vis[i]){
				par[i] = x;
				vis[i] = 1;
				que.push(i);
			}
		}
	}
	assert(vis[y]);
	vector<int> v;
	while(y){
		printf("%d ", y);
		y = par[y];
	}
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=0; i<m; i++){
		int s, e; scanf("%d %d",&s,&e);
		gph[s].push_back(e);
		gph[e].push_back(s);
	}
	for(int i=1; i<=n; i++) sort(gph[i].begin(), gph[i].end());
	priority_queue<pi> pq;
	for(int i=1; i<=n; i++) pq.emplace(cnt[i], i);
	vector<int> ord;
	while(!pq.empty()){
		int x = pq.top().second, y = pq.top().first;
		pq.pop();
		if(cnt[x] != y || idx[x]) continue;
		ord.push_back(x);
		idx[x] = n + 1 - ord.size();
		for(auto &i : gph[x]){
			if(!idx[i]){
				cnt[i]++;
				pq.emplace(cnt[i], i);
			}
		}
	}
	reverse(ord.begin(), ord.end());
	for(auto &i : ord){
		int minBef = 1e9;
		for(auto &j : gph[i]){
			if(idx[j] > idx[i]) minBef = min(minBef, idx[j]);
		}
		minBef--;
		if(minBef < n){
			minBef = ord[minBef];
			for(auto &j : gph[i]){
				if(idx[j] > idx[minBef] && !binary_search(gph[minBef].begin(), gph[minBef].end(), j)){
					report(minBef, i);
					return 0;
				}
			}
		}
	}
	puts("no");
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
indcyc.cpp:44:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int s, e; scanf("%d %d",&s,&e);
             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 520 KB Output is correct
2 Correct 4 ms 504 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1908 KB Output is correct
2 Correct 13 ms 1232 KB Output is correct
3 Correct 29 ms 1880 KB Output is correct
4 Correct 13 ms 1188 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1144 KB Output is correct
2 Correct 13 ms 1144 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 3184 KB Output is correct
2 Correct 51 ms 3208 KB Output is correct
3 Correct 34 ms 2296 KB Output is correct
4 Correct 36 ms 2044 KB Output is correct