oj.uz

Submission #835056

# Submission time Handle Problem Language Result Execution time Memory
835056 2023-08-23T07:14:39 Z arnold518 Highway Tolls (IOI18_highway) C++17
90 / 100
 206 ms 11380 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 9e4;
const int MAXM = 13e4;

int N, M, S, T;
ll A, B, D;
pii E[MAXM+10];
vector<int> adj[MAXN+10];

int vis[MAXN+10];
int P[MAXN+10], PP[MAXN+10];

int TT[MAXM+10];
ll query()
{
	vector<int> V;
	//for(int i=1; i<=M; i++) printf("%d ", TT[i]); printf("\n");
	for(int i=0; i<M; i++) V.push_back(TT[i+1]);
	return ask(V);
}

void find_pair(int _N, vector<int> _U, vector<int> _V, int _A, int _B)
{
	N=_N; M=_U.size();
	for(int i=1; i<=M; i++) E[i]={_U[i-1]+1, _V[i-1]+1};
	for(int i=1; i<=M; i++)
	{
		adj[E[i].first].push_back(E[i].second);
		adj[E[i].second].push_back(E[i].first);
	}
	A=_A; B=_B;

	for(int i=1; i<=M; i++) TT[i]=0;
	D=query()/A;

	int lo=0, hi=M;
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		for(int i=1; i<=M; i++) TT[i]=0;
		for(int i=1; i<=mid; i++) TT[i]=1;
		if(D*A!=query()) hi=mid;
		else lo=mid;
	}

	int cnt=1;
	queue<int> Q;
	Q.push(E[hi].first); vis[E[hi].first]=true;
	Q.push(E[hi].second); vis[E[hi].second]=true;

	while(!Q.empty())
	{
		int now=Q.front(); Q.pop();
		P[now]=cnt++;
		for(auto nxt : adj[now])
		{
			if(vis[nxt]) continue;
			vis[nxt]=true;
			Q.push(nxt);
		}
	}
	for(int i=1; i<=N; i++) PP[P[i]]=i;

	lo=0, hi=N;
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		for(int i=1; i<=M; i++)
		{
			auto [u, v]=E[i];
			if(P[u]<=mid && P[v]<=mid) TT[i]=0;
			else TT[i]=1;
		}
		if(D*A!=query()) lo=mid;
		else hi=mid;
	}
	T=PP[hi];

	cnt=1;
	for(int i=1; i<=N; i++) vis[i]=0;
	Q.push(T); vis[T]=1;
	while(!Q.empty())
	{
		int now=Q.front(); Q.pop();
		P[now]=cnt++;
		for(auto nxt : adj[now])
		{
			if(vis[nxt]) continue;
			vis[nxt]=vis[now]+1;
			Q.push(nxt);
		}
	}
	for(int i=1; i<=N; i++) PP[P[i]]=i;

	lo=0, hi=N;
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		if(vis[PP[mid]]-1<D) lo=mid;
		else if(vis[PP[mid]]-1>D) hi=mid;
		else
		{
			for(int i=1; i<=M; i++)
			{
				auto [u, v]=E[i];
				if(P[u]<=mid && P[v]<=mid) TT[i]=0;
				else TT[i]=1;
			}
			if(D*A!=query()) lo=mid;
			else hi=mid;
		}
	}
	S=PP[hi];

	answer(S-1, T-1);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:46:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   int mid=lo+hi>>1;
      |           ~~^~~
highway.cpp:74:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |   int mid=lo+hi>>1;
      |           ~~^~~
highway.cpp:105:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |   int mid=lo+hi>>1;
      |           ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2432 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2428 KB Output is correct
8 Correct 1 ms 2436 KB Output is correct
9 Correct 1 ms 2432 KB Output is correct
10 Correct 1 ms 2436 KB Output is correct
11 Correct 1 ms 2436 KB Output is correct
12 Correct 1 ms 2384 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2516 KB Output is correct
2 Correct 11 ms 3252 KB Output is correct
3 Correct 121 ms 9888 KB Output is correct
4 Correct 122 ms 9800 KB Output is correct
5 Correct 113 ms 9768 KB Output is correct
6 Correct 108 ms 9792 KB Output is correct
7 Correct 120 ms 9836 KB Output is correct
8 Correct 112 ms 9820 KB Output is correct
9 Correct 113 ms 9828 KB Output is correct
10 Correct 104 ms 9792 KB Output is correct
11 Correct 94 ms 9668 KB Output is correct
12 Correct 117 ms 9636 KB Output is correct
13 Correct 92 ms 9664 KB Output is correct
14 Correct 102 ms 9620 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3152 KB Output is correct
2 Correct 17 ms 4168 KB Output is correct
3 Correct 21 ms 4804 KB Output is correct
4 Correct 70 ms 9616 KB Output is correct
5 Correct 66 ms 9684 KB Output is correct
6 Correct 74 ms 9628 KB Output is correct
7 Correct 127 ms 9708 KB Output is correct
8 Correct 72 ms 9644 KB Output is correct
9 Correct 70 ms 9640 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2512 KB Output is correct
2 Correct 9 ms 3152 KB Output is correct
3 Correct 104 ms 8276 KB Output is correct
4 Correct 88 ms 9772 KB Output is correct
5 Correct 98 ms 9808 KB Output is correct
6 Correct 105 ms 9768 KB Output is correct
7 Correct 81 ms 9828 KB Output is correct
8 Correct 88 ms 9804 KB Output is correct
9 Correct 111 ms 9768 KB Output is correct
10 Correct 140 ms 9804 KB Output is correct
11 Correct 101 ms 9636 KB Output is correct
12 Correct 98 ms 9644 KB Output is correct
13 Correct 115 ms 9632 KB Output is correct
14 Correct 105 ms 9644 KB Output is correct
15 Correct 83 ms 9776 KB Output is correct
16 Correct 93 ms 9780 KB Output is correct
17 Correct 102 ms 9672 KB Output is correct
18 Correct 100 ms 9656 KB Output is correct
19 Correct 91 ms 9768 KB Output is correct
20 Correct 91 ms 9736 KB Output is correct
21 Correct 87 ms 10120 KB Output is correct
22 Correct 102 ms 10108 KB Output is correct
23 Correct 93 ms 10060 KB Output is correct
24 Correct 118 ms 9992 KB Output is correct
25 Correct 114 ms 9724 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3296 KB Output is correct
2 Correct 15 ms 3324 KB Output is correct
3 Correct 146 ms 10200 KB Output is correct
4 Correct 149 ms 10580 KB Output is correct
5 Correct 160 ms 11276 KB Output is correct
6 Correct 157 ms 11380 KB Output is correct
7 Correct 155 ms 11248 KB Output is correct
8 Correct 154 ms 11224 KB Output is correct
9 Correct 138 ms 9008 KB Output is correct
10 Correct 144 ms 9456 KB Output is correct
11 Correct 133 ms 9468 KB Output is correct
12 Correct 155 ms 10828 KB Output is correct
13 Correct 159 ms 11116 KB Output is correct
14 Correct 158 ms 11092 KB Output is correct
15 Correct 187 ms 11116 KB Output is correct
16 Correct 184 ms 9872 KB Output is correct
17 Correct 104 ms 10304 KB Output is correct
18 Correct 118 ms 10332 KB Output is correct
19 Correct 98 ms 10248 KB Output is correct
20 Correct 109 ms 10292 KB Output is correct
21 Correct 157 ms 11128 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3292 KB Output is correct
2 Correct 14 ms 3280 KB Output is correct
3 Correct 162 ms 10200 KB Output is correct
4 Correct 146 ms 10356 KB Output is correct
5 Correct 150 ms 10560 KB Output is correct
6 Correct 158 ms 11272 KB Output is correct
7 Correct 135 ms 10204 KB Output is correct
8 Correct 109 ms 10292 KB Output is correct
9 Partially correct 131 ms 10508 KB Output is partially correct
10 Correct 151 ms 11260 KB Output is correct
11 Correct 171 ms 11220 KB Output is correct
12 Partially correct 161 ms 11368 KB Output is partially correct
13 Correct 107 ms 9460 KB Output is correct
14 Correct 144 ms 9548 KB Output is correct
15 Correct 171 ms 9544 KB Output is correct
16 Correct 99 ms 9460 KB Output is correct
17 Correct 159 ms 9464 KB Output is correct
18 Correct 150 ms 9388 KB Output is correct
19 Correct 172 ms 10604 KB Output is correct
20 Correct 177 ms 10868 KB Output is correct
21 Correct 144 ms 11120 KB Output is correct
22 Correct 156 ms 11164 KB Output is correct
23 Correct 183 ms 11120 KB Output is correct
24 Partially correct 202 ms 11100 KB Output is partially correct
25 Correct 148 ms 11160 KB Output is correct
26 Correct 200 ms 11100 KB Output is correct
27 Partially correct 103 ms 10292 KB Output is partially correct
28 Correct 90 ms 10208 KB Output is correct
29 Partially correct 109 ms 10372 KB Output is partially correct
30 Correct 96 ms 10240 KB Output is correct
31 Correct 114 ms 10240 KB Output is correct
32 Correct 116 ms 10300 KB Output is correct
33 Correct 98 ms 10360 KB Output is correct
34 Correct 106 ms 10208 KB Output is correct
35 Partially correct 129 ms 10232 KB Output is partially correct
36 Correct 93 ms 10160 KB Output is correct
37 Partially correct 148 ms 10340 KB Output is partially correct
38 Correct 97 ms 10284 KB Output is correct
39 Correct 147 ms 11252 KB Output is correct
40 Correct 154 ms 11128 KB Output is correct
41 Correct 174 ms 11172 KB Output is correct
42 Correct 206 ms 11252 KB Output is correct