oj.uz

Submission #102595

# Submission time Handle Problem Language Result Execution time Memory
102595 2019-03-26T05:44:20 Z username Highway Tolls (IOI18_highway) C++14
23 / 100
 349 ms 15748 KB 
#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,o,d1[maxn],d2[maxn],p1[maxn],p2[maxn];
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

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:26: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:40: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:41: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:41: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:42: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:43: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:56: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:57: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:58: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:59: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:77: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:78: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:82: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:83:2: note: in expansion of macro 'REP'
  REP(i,1,v2.size())w[p2[v2[i]]]=0;
  ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6660 KB Output is correct
2 Correct 8 ms 6756 KB Output is correct
3 Correct 8 ms 6696 KB Output is correct
4 Correct 8 ms 6572 KB Output is correct
5 Correct 8 ms 6736 KB Output is correct
6 Correct 8 ms 6756 KB Output is correct
7 Correct 8 ms 6648 KB Output is correct
8 Correct 8 ms 6668 KB Output is correct
9 Correct 8 ms 6664 KB Output is correct
10 Correct 8 ms 6648 KB Output is correct
11 Correct 9 ms 6756 KB Output is correct
12 Correct 7 ms 6660 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6680 KB Output is correct
2 Correct 30 ms 7416 KB Output is correct
3 Correct 231 ms 13852 KB Output is correct
4 Correct 236 ms 13844 KB Output is correct
5 Correct 232 ms 13800 KB Output is correct
6 Correct 239 ms 13920 KB Output is correct
7 Correct 221 ms 13804 KB Output is correct
8 Correct 252 ms 13852 KB Output is correct
9 Correct 231 ms 13980 KB Output is correct
10 Correct 227 ms 13860 KB Output is correct
11 Correct 276 ms 13252 KB Output is correct
12 Correct 275 ms 13296 KB Output is correct
13 Correct 262 ms 13312 KB Output is correct
14 Incorrect 251 ms 13304 KB Output is incorrect: {s, t} is wrong.

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 7372 KB Output is correct
2 Correct 34 ms 8260 KB Output is correct
3 Correct 57 ms 8920 KB Output is correct
4 Correct 172 ms 13176 KB Output is correct
5 Correct 181 ms 13132 KB Output is correct
6 Correct 154 ms 13296 KB Output is correct
7 Correct 157 ms 13296 KB Output is correct
8 Correct 174 ms 13236 KB Output is correct
9 Incorrect 159 ms 13240 KB Output is incorrect: {s, t} is wrong.

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6684 KB Output is correct
2 Correct 24 ms 7500 KB Output is correct
3 Correct 156 ms 12428 KB Output is correct
4 Correct 274 ms 13764 KB Output is correct
5 Correct 191 ms 13844 KB Output is correct
6 Correct 239 ms 13828 KB Output is correct
7 Correct 213 ms 13852 KB Output is correct
8 Correct 201 ms 13880 KB Output is correct
9 Incorrect 215 ms 13844 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 7416 KB Output is correct
2 Correct 34 ms 7544 KB Output is correct
3 Correct 278 ms 14244 KB Output is correct
4 Correct 260 ms 14668 KB Output is correct
5 Correct 317 ms 15612 KB Output is correct
6 Correct 306 ms 15584 KB Output is correct
7 Correct 326 ms 15540 KB Output is correct
8 Correct 322 ms 15544 KB Output is correct
9 Correct 228 ms 12924 KB Output is correct
10 Correct 252 ms 13400 KB Output is correct
11 Correct 255 ms 13804 KB Output is correct
12 Correct 294 ms 14972 KB Output is correct
13 Correct 296 ms 15284 KB Output is correct
14 Correct 341 ms 15616 KB Output is correct
15 Correct 321 ms 15496 KB Output is correct
16 Correct 258 ms 14036 KB Output is correct
17 Correct 215 ms 14264 KB Output is correct
18 Correct 230 ms 14432 KB Output is correct
19 Correct 232 ms 14384 KB Output is correct
20 Correct 209 ms 14372 KB Output is correct
21 Correct 341 ms 15616 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7516 KB Output is correct
2 Correct 43 ms 7592 KB Output is correct
3 Correct 231 ms 14256 KB Output is correct
4 Correct 257 ms 14460 KB Output is correct
5 Correct 279 ms 14752 KB Output is correct
6 Correct 315 ms 15616 KB Output is correct
7 Correct 266 ms 14268 KB Output is correct
8 Correct 297 ms 14368 KB Output is correct
9 Correct 263 ms 14664 KB Output is correct
10 Correct 333 ms 15516 KB Output is correct
11 Correct 349 ms 15552 KB Output is correct
12 Correct 317 ms 15748 KB Output is correct
13 Correct 267 ms 13808 KB Output is correct
14 Correct 245 ms 13320 KB Output is correct
15 Correct 248 ms 13820 KB Output is correct
16 Correct 231 ms 13336 KB Output is correct
17 Correct 238 ms 13824 KB Output is correct
18 Correct 254 ms 13400 KB Output is correct
19 Correct 319 ms 15056 KB Output is correct
20 Correct 295 ms 15288 KB Output is correct
21 Correct 330 ms 15544 KB Output is correct
22 Correct 306 ms 15544 KB Output is correct
23 Correct 325 ms 15588 KB Output is correct
24 Correct 314 ms 15548 KB Output is correct
25 Correct 349 ms 15620 KB Output is correct
26 Correct 328 ms 15556 KB Output is correct
27 Correct 224 ms 14420 KB Output is correct
28 Correct 219 ms 14300 KB Output is correct
29 Correct 227 ms 14512 KB Output is correct
30 Incorrect 184 ms 14360 KB Output is incorrect: {s, t} is wrong.
31 Halted 0 ms 0 KB -