oj.uz

Submission #99352

# Submission time Handle Problem Language Result Execution time Memory
99352 2019-03-02T21:17:13 Z TadijaSebez Highway Tolls (IOI18_highway) C++11
100 / 100
 610 ms 16464 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
const int N=100050;
ll dist;
vector<pair<int,int>> E[N];
vector<int> I[N];
int d[N],f[N];
void AddEdge(int u, int v, int id){ E[u].pb(mp(v,id));E[v].pb(mp(u,id));}
void find_pair(int n, vector<int> U, vector<int> V, int A, int B)
{
	int m=U.size();
	int top=m-1,bot=0,mid,ans;
	vector<int> use(m,0);
	dist=ask(use);
	while(top>=bot)
	{
		mid=top+bot>>1;
		use.clear();use.resize(m);
		for(int i=0;i<=mid;i++) use[i]=1;
		if(ask(use)==dist) bot=mid+1;
		else ans=mid,top=mid-1;
	}
	for(int i=ans+1;i<m;i++) AddEdge(U[i],V[i],i);
	queue<int> q;q.push(U[ans]);q.push(V[ans]);
	d[U[ans]]=d[V[ans]]=1;
	f[U[ans]]=1;f[V[ans]]=2;
	vector<int> L,R;
	while(q.size())
	{
		int x=q.front();q.pop();
		if(f[x]&1) L.pb(x);
		if(f[x]&2) R.pb(x);
		for(auto e:E[x])
		{
			int y=e.first;
			int id=e.second;
			if(!d[y]) d[y]=d[x]+1,f[y]=f[x],q.push(y);
			if(d[y]==d[x]+1)
			{
				//if(f[y]==f[x]) I[y].pb(id);
				//else f[y]|=f[x];
				I[y].pb(id);
				f[y]|=f[x];
			}
		}
	}
	int bad=-1;
	auto Solve=[&](vector<int> vs)
	{
		top=(int)vs.size()-1;bot=0;
		int ret=vs[0];
		vector<int> use;
		while(top>=bot)
		{
			mid=top+bot>>1;
			use.clear();use.resize(m);
			for(int i=0;i<ans;i++) use[i]=1;
			for(int i=mid;i<vs.size();i++) if(vs[i]!=bad) for(int id:I[vs[i]]) use[id]=1;
			if(ask(use)==dist) top=mid-1;
			else ret=vs[mid],bot=mid+1;
		}
		bad=ret;
		return ret;
	};
	return answer(Solve(L),Solve(R));
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:21:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=top+bot>>1;
       ~~~^~~~
highway.cpp: In lambda function:
highway.cpp:59:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid=top+bot>>1;
        ~~~^~~~
highway.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=mid;i<vs.size();i++) if(vs[i]!=bad) for(int id:I[vs[i]]) use[id]=1;
                  ~^~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:28:27: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  queue<int> q;q.push(U[ans]);q.push(V[ans]);
                           ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5024 KB Output is correct
2 Correct 6 ms 5032 KB Output is correct
3 Correct 9 ms 5032 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 5032 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 5100 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 4984 KB Output is correct
10 Correct 6 ms 5024 KB Output is correct
11 Correct 6 ms 5020 KB Output is correct
12 Correct 6 ms 5108 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 23 ms 6108 KB Output is correct
3 Correct 247 ms 13936 KB Output is correct
4 Correct 235 ms 13832 KB Output is correct
5 Correct 281 ms 14724 KB Output is correct
6 Correct 193 ms 12936 KB Output is correct
7 Correct 227 ms 12560 KB Output is correct
8 Correct 275 ms 14860 KB Output is correct
9 Correct 240 ms 12808 KB Output is correct
10 Correct 235 ms 13656 KB Output is correct
11 Correct 176 ms 11088 KB Output is correct
12 Correct 296 ms 13908 KB Output is correct
13 Correct 299 ms 14148 KB Output is correct
14 Correct 281 ms 14292 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5932 KB Output is correct
2 Correct 45 ms 6784 KB Output is correct
3 Correct 58 ms 6016 KB Output is correct
4 Correct 185 ms 11644 KB Output is correct
5 Correct 173 ms 11704 KB Output is correct
6 Correct 172 ms 12808 KB Output is correct
7 Correct 152 ms 7532 KB Output is correct
8 Correct 142 ms 12148 KB Output is correct
9 Correct 149 ms 8972 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 30 ms 5932 KB Output is correct
3 Correct 200 ms 12660 KB Output is correct
4 Correct 267 ms 13744 KB Output is correct
5 Correct 168 ms 10948 KB Output is correct
6 Correct 168 ms 11048 KB Output is correct
7 Correct 250 ms 12580 KB Output is correct
8 Correct 192 ms 11256 KB Output is correct
9 Correct 287 ms 14296 KB Output is correct
10 Correct 247 ms 13316 KB Output is correct
11 Correct 293 ms 14012 KB Output is correct
12 Correct 249 ms 13668 KB Output is correct
13 Correct 289 ms 13148 KB Output is correct
14 Correct 172 ms 11444 KB Output is correct
15 Correct 168 ms 11008 KB Output is correct
16 Correct 159 ms 9492 KB Output is correct
17 Correct 276 ms 13660 KB Output is correct
18 Correct 284 ms 14264 KB Output is correct
19 Correct 170 ms 10276 KB Output is correct
20 Correct 188 ms 10704 KB Output is correct
21 Correct 195 ms 12372 KB Output is correct
22 Correct 188 ms 10048 KB Output is correct
23 Correct 263 ms 15188 KB Output is correct
24 Correct 238 ms 15072 KB Output is correct
25 Correct 241 ms 14348 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 6132 KB Output is correct
2 Correct 44 ms 6128 KB Output is correct
3 Correct 276 ms 15088 KB Output is correct
4 Correct 382 ms 14528 KB Output is correct
5 Correct 418 ms 15020 KB Output is correct
6 Correct 527 ms 16448 KB Output is correct
7 Correct 495 ms 15764 KB Output is correct
8 Correct 364 ms 15168 KB Output is correct
9 Correct 182 ms 8460 KB Output is correct
10 Correct 245 ms 10628 KB Output is correct
11 Correct 270 ms 11692 KB Output is correct
12 Correct 456 ms 15336 KB Output is correct
13 Correct 461 ms 15744 KB Output is correct
14 Correct 542 ms 16188 KB Output is correct
15 Correct 493 ms 16296 KB Output is correct
16 Correct 361 ms 13220 KB Output is correct
17 Correct 233 ms 13980 KB Output is correct
18 Correct 195 ms 11004 KB Output is correct
19 Correct 213 ms 14488 KB Output is correct
20 Correct 196 ms 12544 KB Output is correct
21 Correct 434 ms 16416 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6116 KB Output is correct
2 Correct 33 ms 6128 KB Output is correct
3 Correct 400 ms 15236 KB Output is correct
4 Correct 403 ms 15152 KB Output is correct
5 Correct 379 ms 15112 KB Output is correct
6 Correct 459 ms 15872 KB Output is correct
7 Correct 306 ms 15096 KB Output is correct
8 Correct 381 ms 15460 KB Output is correct
9 Correct 379 ms 14932 KB Output is correct
10 Correct 468 ms 15948 KB Output is correct
11 Correct 610 ms 16464 KB Output is correct
12 Correct 460 ms 16004 KB Output is correct
13 Correct 220 ms 8512 KB Output is correct
14 Correct 232 ms 8368 KB Output is correct
15 Correct 306 ms 13160 KB Output is correct
16 Correct 250 ms 10632 KB Output is correct
17 Correct 283 ms 11676 KB Output is correct
18 Correct 268 ms 10812 KB Output is correct
19 Correct 478 ms 15060 KB Output is correct
20 Correct 491 ms 15820 KB Output is correct
21 Correct 498 ms 16196 KB Output is correct
22 Correct 517 ms 15980 KB Output is correct
23 Correct 510 ms 16300 KB Output is correct
24 Correct 503 ms 16324 KB Output is correct
25 Correct 460 ms 15716 KB Output is correct
26 Correct 508 ms 16340 KB Output is correct
27 Correct 216 ms 12508 KB Output is correct
28 Correct 280 ms 14108 KB Output is correct
29 Correct 292 ms 15552 KB Output is correct
30 Correct 269 ms 15032 KB Output is correct
31 Correct 261 ms 14492 KB Output is correct
32 Correct 264 ms 14536 KB Output is correct
33 Correct 247 ms 15816 KB Output is correct
34 Correct 191 ms 13252 KB Output is correct
35 Correct 220 ms 13876 KB Output is correct
36 Correct 290 ms 14876 KB Output is correct
37 Correct 271 ms 14312 KB Output is correct
38 Correct 250 ms 14672 KB Output is correct
39 Correct 429 ms 16376 KB Output is correct
40 Correct 425 ms 16376 KB Output is correct
41 Correct 320 ms 16372 KB Output is correct
42 Correct 469 ms 16336 KB Output is correct