제출 #137473

#제출 시각아이디문제언어결과실행 시간메모리
137473Angelos통행료 (IOI18_highway)C++11
51 / 100
386 ms31748 KiB
#include "highway.h" #include <bits/stdc++.h> #include <vector> #include <string.h> #define pb push_back #define MAXM 130100 #define MAXN 90100 using namespace std; typedef long long ll; typedef pair<int,int> pii; int toask[MAXM] , M , N , A , B , dpt2[MAXN] , dpt1[MAXN] , vis[MAXN]; int v1[MAXN] , v2[MAXN] , d1[MAXM] , d2[MAXM] , iss , dist; vector<int> w,bad; vector< int > adj[MAXN] , adj1[MAXN] , adj2[MAXN] , deg1[MAXN] , deg2[MAXN] , deg[MAXN]; queue <pii> q1 , q2; ll assk; int toggle(int c){ return (c==0)?1:0; } int bsearch(int arr[]){ //cout << "cool" << endl; vector<int>u,val,ori,ori1;val.clear(); u.clear(); for(int i=0; i<M; i++){ val.pb(0); if(arr[i] == 1) {u.pb(i);} } ll bfo = (iss==1) ? (ll)dist*B:assk; int lo = 0 , hi = u.size()-1; ori.resize(M,0); ori1.resize(M,1); while(lo < hi){ //cout << lo << " " << hi << endl; int mid = (lo+hi)/2; if(iss == 0) {}//val = ori; else val = ori1; for(int i=lo; i<=mid; i++) val[u[i]] = toggle(val[u[i]]); ll cur = ask(val); if(cur == bfo) lo = mid + 1; else hi = mid; bfo = (iss == 0) ? cur : bfo; } //cout << "wow " << lo << " " << u.size() << endl; return u[lo]; } void bfs1(int cur , int d){ queue <pii> q; q.push({cur,0}); while(!q.empty()){ pii tp = q.front();q.pop(); int node = tp.first , dst = tp.second; vis[node] = 1; for(int i=0; i<adj1[node].size(); i++) if(vis[adj1[node][i]] == 0){ q.push({adj1[node][i] , dst+1}); if(dst == d-1) toask[deg1[node][i]] = 1; } } } void bfs2(int cur , int d){ queue <pii> q; q.push({cur,0}); while(!q.empty()){ pii tp = q.front();q.pop(); int node = tp.first , dst = tp.second; vis[node] = 1; for(int i=0; i<adj2[node].size(); i++) if(vis[adj2[node][i]] == 0){ q.push({adj2[node][i] , dst+1}); if(dst == d-1) toask[deg2[node][i]] = 1; } } } void find_pair(int n , vector<int> U , vector<int> V , int a , int b){ M = U.size();N = n;A = a;B=b; for(int i=0; i<M; i++){ adj[U[i]].pb(V[i]); adj[V[i]].pb(U[i]); deg[U[i]].pb(i); deg[V[i]].pb(i); } w.resize(M , 0); assk = ask(w); dist = (int)(assk/(ll)A); //cout << assk << endl; memset(toask , 0 ,sizeof toask); for(int i=0; i<M; i++) toask[i] = 1; int edg = bsearch(toask); q1.push({U[edg],0});q2.push({V[edg],0}); while(!q1.empty() || !q2.empty()){ //cout << q1.size() << " " << q2.size() << endl; if(!q1.empty()){ pii t1 = q1.front();q1.pop(); int cur1 = t1.first; v1[cur1] = 1; d1[cur1] = t1.second; //if(cur1 == 9396 || cur1 == 4410) cout << t1.second << " C" <<endl; for(int i=0; i<adj[cur1].size(); i++){ if(v1[adj[cur1][i]] == 0) { q1.push({adj[cur1][i],t1.second+1}); } } } if(!q2.empty()){ pii t2 = q2.front();q2.pop(); int cur2 = t2.first; //if(cur2 == 9396 || cur2 == 4410) cout << t2.second << " C" <<endl; v2[cur2] = 1; d2[cur2] = t2.second; for(int i=0; i<adj[cur2].size(); i++){ if(v2[adj[cur2][i]] == 0) { q2.push({adj[cur2][i],t2.second+1}); } } } } //cout << d1[70535] << " " << d1[1479] << endl; //cout << d2[70535] << " " << d2[1479] << endl; //cout << "cool2" << endl; for(int i=0; i<M; i++){ //cout << i << " " << d1[U[i]] << " " << d1[V[i]] << " " << d2[U[i]] << " " << d2[V[i]] << endl; if(d1[U[i]] < d2[U[i]] && d1[V[i]] < d2[V[i]]) { //f(U[i] == 4410 || V[i] == 4410 || U[i] == 9396 || V[i] == 9396)cout << "1 : " << i << endl; adj1[U[i]].pb(V[i]); adj1[V[i]].pb(U[i]); deg1[U[i]].pb(i); deg1[V[i]].pb(i); } else if(d1[U[i]] > d2[U[i]] && d1[V[i]] > d2[V[i]]) { //if(U[i] == 4410 || V[i] == 4410 || U[i] == 9396 || V[i] == 9396)cout << "2 : " << i << endl; adj2[U[i]].pb(V[i]); adj2[V[i]].pb(U[i]); deg2[U[i]].pb(i); deg2[V[i]].pb(i); } else{ if(i != edg)bad.push_back(i); } } for(int i=0; i<M; i++) w[i] = 0; for(int i=0; i<N; i++) for(int j=0; j<adj1[i].size(); j++) w[deg1[i][j]] = 1; for(int i=0; i<bad.size(); i++) w[bad[i]] = 1; ll assk1 = ask(w); for(int i=0; i<M; i++) w[i] = 0; for(int i=0; i<N; i++) for(int j=0; j<adj2[i].size(); j++) w[deg2[i][j]] = 1; for(int i=0; i<bad.size(); i++) w[bad[i]] = 1; ll assk2 = ask(w); int patu1 = (int)(((ll)assk1-assk)/((ll)B-A)); int patv1 = dist - patu1 - 1; int patv2 = (int)(((ll)assk2-assk)/((ll)B-A)); int patu2 = dist - patv2 - 1; int patu=patu1 , patv = patv1; if(patu1 != patu2){ if(assk1 <= assk2) patu=patu1,patv=patv1; else patu=patu2,patv=patv2; } //cout << assk1 << " " << assk2 << " " << edg << " " << U[edg] << " " << V[edg] << " " << dist << " " << patu << " " << patv << endl; int edgu ,edgv , s , t; if(patu != 0){ memset(toask , 0 ,sizeof toask); //for(int i=0; i<bad.size(); i++) toask[bad[i]] = 1; memset(vis , 0 ,sizeof vis); bfs1(U[edg] , patu); iss = 1; edgu = bsearch(toask); if(d1[U[edgu]] > d1[V[edgu]]) s = U[edgu]; else s = V[edgu]; } else s = U[edg]; if(patv != 0){ memset(toask , 0 , sizeof toask); //for(int i=0; i<bad.size(); i++) toask[bad[i]] = 1; memset(vis , 0 ,sizeof vis); bfs2(V[edg] , patv); edgv = bsearch(toask); if(d2[U[edgv]] > d2[V[edgv]]) t = U[edgv]; else t = V[edgv]; } else t = V[edg]; //cout << s << " " << t << endl; answer(s,t); }

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

highway.cpp: In function 'void bfs1(int, int)':
highway.cpp:65:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<adj1[node].size(); i++)
                      ~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void bfs2(int, int)':
highway.cpp:82:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<adj2[node].size(); i++)
                      ~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:127:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0; i<adj[cur1].size(); i++){
                          ~^~~~~~~~~~~~~~~~~
highway.cpp:140:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0; i<adj[cur2].size(); i++){
                          ~^~~~~~~~~~~~~~~~~
highway.cpp:182:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<adj1[i].size(); j++) w[deg1[i][j]] = 1;
                      ~^~~~~~~~~~~~~~~
highway.cpp:183:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<bad.size(); i++) w[bad[i]] = 1;
                  ~^~~~~~~~~~~
highway.cpp:188:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<adj2[i].size(); j++) w[deg2[i][j]] = 1;
                      ~^~~~~~~~~~~~~~~
highway.cpp:189:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<bad.size(); i++) w[bad[i]] = 1;
                  ~^~~~~~~~~~~
#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...