제출 #229551

#제출 시각아이디문제언어결과실행 시간메모리
229551FieryPhoenixTeleporters (IOI08_teleporters)C++11
90 / 100
477 ms51688 KiB
#include <bits/stdc++.h> using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef long long ll; typedef long double ld; #define INF 2001001001 #define MOD 1000000007 int N,M; int L[1000001],R[1000001]; int adj[2000005]; int tele[2000005]; int label[2000005]; bool vis[2000005]; int ans=0; int cycleSize; vector<int>cyc; void dfs(int node, int from){ vis[node]=true; if (!vis[adj[node]]){ cycleSize++; if (from==1) ans++; dfs(adj[node],from); } } int main() { //ios_base::sync_with_stdio(0);cin.tie(0); //freopen (".in","r",stdin); //freopen (".out","w",stdout); scanf("%d%d",&N,&M); for (int i=1;i<=N;i++){ scanf("%d%d",&L[i],&R[i]); tele[L[i]]=i; tele[R[i]]=i; } int cnt=0; for (int i=1;i<=2000000;i++){ if (tele[i]!=0){ cnt++; label[i]=cnt; } } for (int i=1;i<=2000000;i++){ if (tele[i]!=0){ if (L[tele[i]]==i) adj[label[i]-1]=label[R[tele[i]]]; else adj[label[i]-1]=label[L[tele[i]]]; } } dfs(1,1); for (int i=2;i<=N*2;i++) if (!vis[i]){ cycleSize=0; dfs(i,i); cyc.push_back(cycleSize+1); } sort(cyc.begin(),cyc.end()); reverse(cyc.begin(),cyc.end()); /* cout<<ans<<endl; cout<<"CYCLES: "; for (int x:cyc) cout<<x<<' '; cout<<endl; */ for (int i=0;i<(int)cyc.size();i++){ if (M>0){ ans+=cyc[i]+2; M--; } } while (M>=2){ M-=2; ans+=4; } if (M==1) ans++; cout<<ans<<endl; return 0; }

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

teleporters.cpp: In function 'int main()':
teleporters.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&N,&M);
   ~~~~~^~~~~~~~~~~~~~
teleporters.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&L[i],&R[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~
#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...
#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...