oj.uz

Submission #99351

# Submission time Handle Problem Language Result Execution time Memory
99351 2019-03-02T21:15:22 Z TadijaSebez Highway Tolls (IOI18_highway) C++11
100 / 100
 503 ms 16496 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];
			}
		}
	}
	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:57:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid=top+bot>>1;
        ~~~^~~~
highway.cpp:60: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 5028 KB Output is correct
2 Correct 6 ms 5024 KB Output is correct
3 Correct 6 ms 5024 KB Output is correct
4 Correct 6 ms 5016 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 4940 KB Output is correct
8 Correct 6 ms 4984 KB Output is correct
9 Correct 6 ms 5104 KB Output is correct
10 Correct 6 ms 5020 KB Output is correct
11 Correct 6 ms 4984 KB Output is correct
12 Correct 6 ms 5024 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 29 ms 6008 KB Output is correct
3 Correct 240 ms 13940 KB Output is correct
4 Correct 247 ms 13828 KB Output is correct
5 Correct 256 ms 14820 KB Output is correct
6 Correct 175 ms 12932 KB Output is correct
7 Correct 198 ms 12572 KB Output is correct
8 Correct 293 ms 14776 KB Output is correct
9 Correct 250 ms 12780 KB Output is correct
10 Correct 228 ms 13708 KB Output is correct
11 Correct 183 ms 11128 KB Output is correct
12 Correct 309 ms 13896 KB Output is correct
13 Correct 293 ms 14180 KB Output is correct
14 Correct 298 ms 14236 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5860 KB Output is correct
2 Correct 45 ms 6784 KB Output is correct
3 Correct 46 ms 6056 KB Output is correct
4 Correct 173 ms 11528 KB Output is correct
5 Correct 185 ms 11608 KB Output is correct
6 Correct 193 ms 12808 KB Output is correct
7 Correct 166 ms 7572 KB Output is correct
8 Correct 164 ms 12136 KB Output is correct
9 Correct 150 ms 8972 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5032 KB Output is correct
2 Correct 51 ms 5860 KB Output is correct
3 Correct 205 ms 12628 KB Output is correct
4 Correct 264 ms 13840 KB Output is correct
5 Correct 182 ms 10788 KB Output is correct
6 Correct 155 ms 11088 KB Output is correct
7 Correct 229 ms 12640 KB Output is correct
8 Correct 184 ms 11188 KB Output is correct
9 Correct 266 ms 14196 KB Output is correct
10 Correct 236 ms 13232 KB Output is correct
11 Correct 263 ms 14076 KB Output is correct
12 Correct 252 ms 13684 KB Output is correct
13 Correct 260 ms 13172 KB Output is correct
14 Correct 185 ms 11480 KB Output is correct
15 Correct 175 ms 10952 KB Output is correct
16 Correct 163 ms 9424 KB Output is correct
17 Correct 272 ms 13716 KB Output is correct
18 Correct 344 ms 14224 KB Output is correct
19 Correct 182 ms 10368 KB Output is correct
20 Correct 167 ms 10896 KB Output is correct
21 Correct 220 ms 12380 KB Output is correct
22 Correct 196 ms 9940 KB Output is correct
23 Correct 241 ms 15280 KB Output is correct
24 Correct 219 ms 15084 KB Output is correct
25 Correct 275 ms 14328 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 6124 KB Output is correct
2 Correct 25 ms 6024 KB Output is correct
3 Correct 243 ms 15092 KB Output is correct
4 Correct 369 ms 14524 KB Output is correct
5 Correct 416 ms 15144 KB Output is correct
6 Correct 449 ms 16384 KB Output is correct
7 Correct 447 ms 15792 KB Output is correct
8 Correct 385 ms 15208 KB Output is correct
9 Correct 235 ms 8468 KB Output is correct
10 Correct 252 ms 10620 KB Output is correct
11 Correct 287 ms 11648 KB Output is correct
12 Correct 384 ms 15344 KB Output is correct
13 Correct 442 ms 15820 KB Output is correct
14 Correct 455 ms 16188 KB Output is correct
15 Correct 495 ms 16372 KB Output is correct
16 Correct 360 ms 13296 KB Output is correct
17 Correct 257 ms 13972 KB Output is correct
18 Correct 134 ms 11000 KB Output is correct
19 Correct 222 ms 14584 KB Output is correct
20 Correct 196 ms 12636 KB Output is correct
21 Correct 451 ms 16496 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 6112 KB Output is correct
2 Correct 34 ms 6148 KB Output is correct
3 Correct 349 ms 15284 KB Output is correct
4 Correct 382 ms 15168 KB Output is correct
5 Correct 377 ms 15180 KB Output is correct
6 Correct 423 ms 15840 KB Output is correct
7 Correct 324 ms 15252 KB Output is correct
8 Correct 340 ms 15544 KB Output is correct
9 Correct 343 ms 15032 KB Output is correct
10 Correct 449 ms 15936 KB Output is correct
11 Correct 503 ms 16444 KB Output is correct
12 Correct 438 ms 16032 KB Output is correct
13 Correct 231 ms 8472 KB Output is correct
14 Correct 240 ms 8344 KB Output is correct
15 Correct 300 ms 13204 KB Output is correct
16 Correct 270 ms 10724 KB Output is correct
17 Correct 286 ms 11624 KB Output is correct
18 Correct 292 ms 10812 KB Output is correct
19 Correct 437 ms 14992 KB Output is correct
20 Correct 456 ms 15844 KB Output is correct
21 Correct 457 ms 16188 KB Output is correct
22 Correct 461 ms 15988 KB Output is correct
23 Correct 491 ms 16320 KB Output is correct
24 Correct 476 ms 16388 KB Output is correct
25 Correct 424 ms 15808 KB Output is correct
26 Correct 479 ms 16236 KB Output is correct
27 Correct 213 ms 12496 KB Output is correct
28 Correct 247 ms 14084 KB Output is correct
29 Correct 256 ms 15608 KB Output is correct
30 Correct 248 ms 15140 KB Output is correct
31 Correct 263 ms 14568 KB Output is correct
32 Correct 263 ms 14544 KB Output is correct
33 Correct 232 ms 15772 KB Output is correct
34 Correct 224 ms 13340 KB Output is correct
35 Correct 213 ms 13872 KB Output is correct
36 Correct 258 ms 14808 KB Output is correct
37 Correct 266 ms 14296 KB Output is correct
38 Correct 239 ms 14660 KB Output is correct
39 Correct 439 ms 16372 KB Output is correct
40 Correct 408 ms 16388 KB Output is correct
41 Correct 300 ms 16360 KB Output is correct
42 Correct 465 ms 16344 KB Output is correct