제출 #97857

#제출 시각아이디문제언어결과실행 시간메모리
97857Retro3014Potemkin cycle (CEOI15_indcyc)C++17
80 / 100
1084 ms5188 KiB
#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(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; }

컴파일 시 표준 에러 (stderr) 메시지

indcyc.cpp: In function 'int main()':
indcyc.cpp:102:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<gp[i].size(); j++){
                ~^~~~~~~~~~~~~
indcyc.cpp:108:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j2=j+1; j2<gp[i].size(); j2++){
                    ~~^~~~~~~~~~~~~
indcyc.cpp:111: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);
             ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...