oj.uz

Submission #130688

# Submission time Handle Problem Language Result Execution time Memory
130688 2019-07-15T20:26:40 Z mahmoudbadawy Highway Tolls (IOI18_highway) C++17
51 / 100
 320 ms 10872 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

const int N=1e5+5;

vector<int> v;
int vis[N];
vector<pair<int,int> > adj[N];
int par[N];

long long query(int l,int r,int m)
{
	vector<int> vv(m,1);
	for(int i=l;i<=r;i++)
		vv[abs(v[i])-1]=0;
	return ask(vv);
}

void find_pair(int n, std::vector<int> U, std::vector<int> V, int a, int b) 
{
	int m=U.size();
	for(int i=0;i<m;i++)
	{
		adj[U[i]].push_back({V[i],(i+1)});
		adj[V[i]].push_back({U[i],-(i+1)});
	}
	vector<int> anss;
	int root=0;
	for(int x=0;x<2;x++)
	{
		queue<int> q; v.clear();
		memset(vis,0,sizeof vis);
		q.push(root); vis[root]=1;
		while(q.size())
		{
			int x=q.front();
			q.pop();
			for(auto i:adj[x])
	  		{
	  			if(vis[i.first]) continue;
	  			v.push_back(i.second);
	  			q.push(i.first);
	  			par[i.first]=x;
	  			vis[i.first]=1;
	  		}
	  	}
	  	reverse(v.begin(), v.end());
	  	long long f=query(0,v.size()-1,m);
	  	/*for(int i=0;i<v.size();i++)
	  		cout << v[i] << " ";
	  	cout << endl;*/
	  	int st=0,en=v.size()-1,ans=0;
	  	while(st<=en)
	  	{
	  		int mid=(st+en)/2;
	  		if(query(mid,v.size()-1,m)==f)
	  		{
	  			ans=mid; st=mid+1;
	  		}
	  		else
	  			en=mid-1;
	  	}
	  	int s=v[ans]>0?V[v[ans]-1]:U[-v[ans]-1];
	  	root=s; anss.push_back(s);
	}
	//cout << anss[0] << " " << anss[1] << endl;
  	answer(anss[0],anss[1]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2936 KB Output is correct
2 Correct 5 ms 3064 KB Output is correct
3 Correct 4 ms 3064 KB Output is correct
4 Correct 4 ms 3064 KB Output is correct
5 Correct 5 ms 3064 KB Output is correct
6 Correct 4 ms 3088 KB Output is correct
7 Correct 5 ms 3064 KB Output is correct
8 Correct 4 ms 2940 KB Output is correct
9 Correct 4 ms 3064 KB Output is correct
10 Correct 5 ms 3064 KB Output is correct
11 Correct 5 ms 3064 KB Output is correct
12 Correct 4 ms 2976 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3192 KB Output is correct
2 Correct 16 ms 3800 KB Output is correct
3 Correct 217 ms 9076 KB Output is correct
4 Correct 212 ms 9176 KB Output is correct
5 Correct 213 ms 9076 KB Output is correct
6 Correct 194 ms 9044 KB Output is correct
7 Correct 213 ms 9028 KB Output is correct
8 Correct 217 ms 9084 KB Output is correct
9 Correct 203 ms 9052 KB Output is correct
10 Correct 227 ms 9052 KB Output is correct
11 Correct 209 ms 8488 KB Output is correct
12 Correct 249 ms 8388 KB Output is correct
13 Correct 210 ms 8488 KB Output is correct
14 Correct 200 ms 8380 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3768 KB Output is correct
2 Correct 43 ms 4360 KB Output is correct
3 Correct 67 ms 4960 KB Output is correct
4 Correct 163 ms 8464 KB Output is correct
5 Correct 155 ms 8448 KB Output is correct
6 Correct 171 ms 8368 KB Output is correct
7 Correct 154 ms 8372 KB Output is correct
8 Correct 164 ms 8468 KB Output is correct
9 Correct 156 ms 8376 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3112 KB Output is correct
2 Correct 22 ms 3640 KB Output is correct
3 Correct 156 ms 7748 KB Output is correct
4 Correct 220 ms 9080 KB Output is correct
5 Correct 201 ms 9000 KB Output is correct
6 Correct 207 ms 9056 KB Output is correct
7 Correct 229 ms 9056 KB Output is correct
8 Correct 212 ms 8984 KB Output is correct
9 Correct 209 ms 9040 KB Output is correct
10 Correct 223 ms 9080 KB Output is correct
11 Correct 227 ms 8452 KB Output is correct
12 Correct 224 ms 8372 KB Output is correct
13 Correct 221 ms 8464 KB Output is correct
14 Correct 214 ms 8444 KB Output is correct
15 Correct 206 ms 9052 KB Output is correct
16 Correct 182 ms 8992 KB Output is correct
17 Correct 226 ms 8396 KB Output is correct
18 Correct 226 ms 8388 KB Output is correct
19 Correct 213 ms 9076 KB Output is correct
20 Correct 220 ms 8484 KB Output is correct
21 Correct 164 ms 9604 KB Output is correct
22 Correct 208 ms 9604 KB Output is correct
23 Correct 180 ms 9240 KB Output is correct
24 Correct 185 ms 9268 KB Output is correct
25 Correct 226 ms 8500 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3652 KB Output is correct
2 Correct 29 ms 3776 KB Output is correct
3 Correct 249 ms 9548 KB Output is correct
4 Correct 235 ms 9816 KB Output is correct
5 Correct 320 ms 10872 KB Output is correct
6 Correct 319 ms 10808 KB Output is correct
7 Incorrect 291 ms 10764 KB Output is incorrect: {s, t} is wrong.
8 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 3764 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -