oj.uz

답안 #97858

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97858 2019-02-19T03:28:08 Z Retro3014 Potemkin cycle (CEOI15_indcyc) C++17
100 / 100
 902 ms 5236 KB 
#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 1000;
const int MAX_M = 100000;

int N, M;
vector<int> gp[MAX_N+1];
vector<pii> edge;
bool chk[MAX_N+1];
bool chk2[MAX_N+1];
bool chkg[MAX_N+1];
int g[MAX_N+1];

int find_g(int x){
	if(x==g[x])	return x;
	return g[x] = find_g(g[x]);
}

void union_g(int x, int y){
	x = find_g(x), y = find_g(y);
	g[x] = y;
}

int from[MAX_N+1];
deque<int> dq;

void answer(int x, int y, int z){
	from[y] = x; from[z] = y;
	dq.pb(z);
	while(!dq.empty()){
		int now = dq.front();
		dq.pop_front();
		if(now==x)	break;
		for(auto i : gp[now]){
			if(i==x || !chk[i]){
				if(from[i]==0){
					from[i] = now; dq.push_back(i);
				}
			}
		}
	}
	while(1){
		printf("%d ", x); if(x==y)	break;
		x = from[x];
	}
}

int check[MAX_N+1][MAX_N+1];
vector<int> gnum;
int ivgn[MAX_N+1];

int main(){
	scanf("%d%d", &N, &M);
	rep(i, M){
		int a, b; scanf("%d%d", &a, &b);
		gp[a].pb(b); gp[b].pb(a);
		edge.pb({a, b});
	}
	rep(i, N){
		rep(j, N)	g[j] = j;
		chk[i] = true;
		for(auto j: gp[i])	chk[j] = true;
		for(auto p : edge){
			if(chk[p.first] || chk[p.second])	continue;
			union_g(p.first, p.second);
		}
		gnum.clear();
		for(int j=1; j<=N; j++){
			if(chk[j])	continue;
			if(find_g(j) == j){
				gnum.push_back(j);
				ivgn[j] = gnum.size()-1;
			}
		}
		for(auto p : edge){
			if(chk[p.first] && !chk[p.second]){
				check[p.first][ivgn[find_g(p.second)]] = true;
			}else if(!chk[p.first] && chk[p.second]){
				check[p.second][ivgn[find_g(p.first)]] = true;
			}
		}
		for(int j=0; j<gp[i].size(); j++){
			int now = gp[i][j];
			for(auto k : gp[now]){
				if(chk[k])	chk2[k] = true;
				else	chkg[find_g(k)] = true;
			}
			for(int j2=j+1; j2<gp[i].size(); j2++){
				int now2 = gp[i][j2];
				if(now2==now || chk2[now2])	continue;
				for(int k = 0; k<gnum.size(); k++){
					if(check[now][k] && check[now2][k]){
						answer(now, i, now2);
						return 0;
					}
				}
			}
			for(auto k : gp[now]){
				if(chk[k])	chk2[k] = false;
				else	chkg[find_g(k)] = false;
			}
		}
		for(auto p : edge){
			if(chk[p.first] && !chk[p.second]){
				check[p.first][ivgn[find_g(p.second)]] = false;
			}else if(!chk[p.first] && chk[p.second]){
				check[p.second][ivgn[find_g(p.first)]] = false;
			}
		}
		for(auto j : gp[i])	chk[j] = false;
		chk[i] = false;
	}
	printf("no");	return 0;
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:103:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<gp[i].size(); j++){
                ~^~~~~~~~~~~~~
indcyc.cpp:109:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j2=j+1; j2<gp[i].size(); j2++){
                    ~~^~~~~~~~~~~~~
indcyc.cpp:112:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k = 0; k<gnum.size(); k++){
                    ~^~~~~~~~~~~~
indcyc.cpp:74: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:76:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 6 ms 640 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 1536 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 6 ms 768 KB Output is correct
4 Correct 42 ms 1536 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 25 ms 1280 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 3184 KB Output is correct
2 Correct 12 ms 2172 KB Output is correct
3 Correct 516 ms 5164 KB Output is correct
4 Correct 250 ms 4728 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 1536 KB Output is correct
2 Correct 509 ms 3740 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 3792 KB Output is correct
2 Correct 399 ms 2168 KB Output is correct
3 Correct 61 ms 2672 KB Output is correct
4 Correct 902 ms 5236 KB Output is correct