제출 #235921

#제출 시각아이디문제언어결과실행 시간메모리
235921laoriu통행료 (IOI18_highway)C++14
0 / 100
28 ms15992 KiB
#include <bits/stdc++.h> #include "highway.h" using namespace std; typedef pair <int,int> pp; int n,m,l,vs[200002],D[2][200002]; vector <pp> P[200002],adj[200002],A[200002]; pp B[200002]; vector <int> ds,sub[2],w; int ss,tt,aa,bb; void build_tree(int x,int u,int v) { memset(vs,0,sizeof(vs)); queue <int> q; adj[u].push_back({v,x});adj[v].push_back({u,x}); q.push(u);q.push(v);vs[u]=vs[v]=1;ds.push_back(x); while (!q.empty()) { int u=q.front(); q.pop(); for (int i=0;i<A[u].size();i++) { int v=A[u][i].first; int x=A[u][i].second; if (vs[v]==1) continue; adj[u].push_back({v,x}); vs[v]=1; ds.push_back(x); } } } void bfs(int p,int u,int ban) { queue <int> q; for (int i=0;i<n;i++) D[p][i]=1e9; memset(vs,0,sizeof(vs)); q.push(u);D[p][u]=0;vs[u]=1; while (!q.empty()) { int u=q.front(); q.pop(); for (int i=0;i<adj[u].size();i++) { int v=adj[u][i].first; int x=adj[u][i].second; if (vs[v]==1||x==ban) continue; vs[v]=1;D[p][v]=D[p][u]+1; sub[p].push_back(x); } } } int find1(int p,int s,int l) { if (l==0) return s; vector <int> X; for (int i=0;i<sub[p].size();i++) { int u=B[sub[p][i]].first; int v=B[sub[p][i]].second; if (D[p][u]>D[p][v]) swap(u,v); if (D[p][u]==l-1&&D[p][v]==l) { X.push_back(sub[p][i]); } } int d=0;int c=X.size()-1; vector <int> w;w.resize(m,0); int ans=0; while (d<=c) { int mid=(d+c)/2; for (int i=0;i<m;i++) w[i]=1; for (int i=0;i<=mid;i++) w[X[i]]=0; if (ask(w)<(long long)bb*l) { c=mid-1; ans=X[mid]; } else d=mid+1; } int u=B[ans].first;int v=B[ans].second; if (D[p][u]==l) return u;else return v; } void find_pair(int n,vector <int> U,vector <int> V,int a,int b) { aa=a;bb=b; m=U.size(); for (int i=0;i<U.size();i++) { A[U[i]].push_back({V[i],i}); A[V[i]].push_back({U[i],i}); B[i]={U[i],V[i]}; } w.resize(m,0); long long t=ask(w);l=t/a; int d=0;int c=m-1;int x; while (d<=c) { int mid=(d+c)/2; for (int i=0;i<m;i++) if (i<=mid) w[i]=0;else w[i]=1; if (ask(w)==t) { x=mid; c=mid-1; } else d=mid+1; } int u=U[x];int v=V[x]; build_tree(x,u,v); bfs(0,u,x);bfs(1,v,x); for (int i=0;i<m;i++) w[i]=1; for (int i=0;i<sub[0].size();i++) w[sub[0][i]]=0; int l1; t=ask(w); for (int i=0;i<=l-1;i++) if ((long long) a*i+(long long) b*(l-i)==t) l1=i; int l2=l-1-l1; //cout<<l1<<' '<<l2<<endl; answer(find1(0,u,l1),find1(1,v,l2)); }

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

highway.cpp: In function 'void build_tree(int, int, int)':
highway.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<A[u].size();i++)
                      ~^~~~~~~~~~~~
highway.cpp: In function 'void bfs(int, int, int)':
highway.cpp:46:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<adj[u].size();i++)
                      ~^~~~~~~~~~~~~~
highway.cpp: In function 'int find1(int, int, int)':
highway.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<sub[p].size();i++)
                  ~^~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:94:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<U.size();i++)
                  ~^~~~~~~~~
highway.cpp:121:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<sub[0].size();i++)
                  ~^~~~~~~~~~~~~~
highway.cpp:129:11: warning: 'l1' may be used uninitialized in this function [-Wmaybe-uninitialized]
     answer(find1(0,u,l1),find1(1,v,l2));
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:115:14: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int u=U[x];int v=V[x];
              ^
#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...