Submission #102604

#	Time	Username	Problem	Language	Result	Execution time	Memory
102604		username	Highway Tolls (IOI18_highway)	C++14	100 / 100	356 ms	15676 KiB

highway

#include<bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> VI;
#define REP(i,j,k) for(register int i=(j);i<(k);++i)
#define RREP(i,j,k) for(register int i=(j)-1;i>=(k);--i)
#define ALL(a) a.begin(),a.end()
#define MST(a,v) memset(a,(v),sizeof a)
#define pb push_back
#define mid (l+r>>1)


const int maxn=9e4+9,inf=1<<30;
int n,m,d1[maxn],d2[maxn],p1[maxn],p2[maxn];
long long o;
vector<pii>G[maxn];
VI g1[maxn],g2[maxn],w;
queue<int>Q;

void bfs(int s,int*dis,int*par){
	fill(dis,dis+n,inf);
	dis[s]=0;
	Q.push(s);
	while(!Q.empty()){
		int u=Q.front();Q.pop();
		REP(i,0,G[u].size()){
			int v=G[u][i].first;
			if(dis[v]>dis[u]+1){
				dis[v]=dis[u]+1;
				par[v]=G[u][i].second;
				Q.push(v);
			}
		}
	}
}

int find(VI&vt,int*par){
	int l=0,r=vt.size();
	while(l+1<r){
		REP(i,1,mid)w[par[vt[i]]]=0;
		REP(i,mid,vt.size())w[par[vt[i]]]=1;
		if(ask(w)>o)l=mid;
		else r=mid;
	}
	return vt[l];
}

void find_pair(int _n,VI uu,VI vv,int a,int b){
	n=_n;
	m=uu.size();
	w.resize(m);
	REP(i,0,m)w[i]=0;
	o=ask(w);
	int l=0,r=m;
	while(l+1<r){
		REP(i,0,mid)w[i]=0;
		REP(i,mid,m)w[i]=1;
		if(ask(w)>o)l=mid;
		else r=mid;
	}
	int ee=l;
	REP(i,0,m){
		int u=uu[i],v=vv[i];
		G[u].pb(pii(v,i)),G[v].pb(pii(u,i));
	}
	bfs(uu[ee],d1,p1);
	bfs(vv[ee],d2,p2);
	VI v1,v2;
	REP(i,0,n){
		if(d1[i]<d2[i])v1.pb(i);
		else v2.pb(i);
	}
	sort(ALL(v1),[](int x,int y){return d1[x]<d1[y];});
	sort(ALL(v2),[](int x,int y){return d2[x]<d2[y];});
	REP(i,0,m)w[i]=1;
	w[ee]=0;
	REP(i,1,v1.size())w[p1[v1[i]]]=0;
	REP(i,1,v2.size())w[p2[v2[i]]]=0;
	int u=find(v1,p1);
	REP(i,0,m)w[i]=1;
	w[ee]=0;
	REP(i,1,v1.size())w[p1[v1[i]]]=0;
	REP(i,1,v2.size())w[p2[v2[i]]]=0;
	int v=find(v2,p2);
	answer(u,v);
}

Compilation message (stderr)

highway.cpp: In function 'void bfs(int, int*, int*)':
highway.cpp:6:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(register int i=(j);i<(k);++i)
                                            ^
highway.cpp:27:3: note: in expansion of macro 'REP'
   REP(i,0,G[u].size()){
   ^~~
highway.cpp: In function 'int find(VI&, int*)':
highway.cpp:11:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
highway.cpp:6:46: note: in definition of macro 'REP'
 #define REP(i,j,k) for(register int i=(j);i<(k);++i)
                                              ^
highway.cpp:41:11: note: in expansion of macro 'mid'
   REP(i,1,mid)w[par[vt[i]]]=0;
           ^~~
highway.cpp:11:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
highway.cpp:6:40: note: in definition of macro 'REP'
 #define REP(i,j,k) for(register int i=(j);i<(k);++i)
                                        ^
highway.cpp:42:9: note: in expansion of macro 'mid'
   REP(i,mid,vt.size())w[par[vt[i]]]=1;
         ^~~
highway.cpp:6:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(register int i=(j);i<(k);++i)
                                            ^
highway.cpp:42:3: note: in expansion of macro 'REP'
   REP(i,mid,vt.size())w[par[vt[i]]]=1;
   ^~~
highway.cpp:11:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
highway.cpp:43:17: note: in expansion of macro 'mid'
   if(ask(w)>o)l=mid;
                 ^~~
highway.cpp:11:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
highway.cpp:44:10: note: in expansion of macro 'mid'
   else r=mid;
          ^~~
highway.cpp: In function 'void find_pair(int, VI, VI, int, int)':
highway.cpp:11:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
highway.cpp:6:46: note: in definition of macro 'REP'
 #define REP(i,j,k) for(register int i=(j);i<(k);++i)
                                              ^
highway.cpp:57:11: note: in expansion of macro 'mid'
   REP(i,0,mid)w[i]=0;
           ^~~
highway.cpp:11:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
highway.cpp:6:40: note: in definition of macro 'REP'
 #define REP(i,j,k) for(register int i=(j);i<(k);++i)
                                        ^
highway.cpp:58:9: note: in expansion of macro 'mid'
   REP(i,mid,m)w[i]=1;
         ^~~
highway.cpp:11:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
highway.cpp:59:17: note: in expansion of macro 'mid'
   if(ask(w)>o)l=mid;
                 ^~~
highway.cpp:11:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
highway.cpp:60:10: note: in expansion of macro 'mid'
   else r=mid;
          ^~~
highway.cpp:6:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(register int i=(j);i<(k);++i)
                                            ^
highway.cpp:78:2: note: in expansion of macro 'REP'
  REP(i,1,v1.size())w[p1[v1[i]]]=0;
  ^~~
highway.cpp:6:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(register int i=(j);i<(k);++i)
                                            ^
highway.cpp:79:2: note: in expansion of macro 'REP'
  REP(i,1,v2.size())w[p2[v2[i]]]=0;
  ^~~
highway.cpp:6:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(register int i=(j);i<(k);++i)
                                            ^
highway.cpp:83:2: note: in expansion of macro 'REP'
  REP(i,1,v1.size())w[p1[v1[i]]]=0;
  ^~~
highway.cpp:6:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(register int i=(j);i<(k);++i)
                                            ^
highway.cpp:84:2: note: in expansion of macro 'REP'
  REP(i,1,v2.size())w[p2[v2[i]]]=0;
  ^~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 18 / 18
• Subtask 6: 31 / 31