oj.uz

Submission #835058

# Submission time Handle Problem Language Result Execution time Memory
835058 2023-08-23T07:21:32 Z arnold518 Highway Tolls (IOI18_highway) C++17
90 / 100
 194 ms 11364 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]=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+1)/2) 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;
		}
	}
	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:73:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |   int mid=lo+hi>>1;
      |           ~~^~~
highway.cpp:109:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |   int mid=lo+hi>>1;
      |           ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 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 2384 KB Output is correct
8 Correct 1 ms 2432 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 1 ms 2436 KB Output is correct
11 Correct 2 ms 2384 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 2 ms 2492 KB Output is correct
2 Correct 9 ms 3152 KB Output is correct
3 Correct 118 ms 9808 KB Output is correct
4 Correct 125 ms 9772 KB Output is correct
5 Correct 110 ms 9928 KB Output is correct
6 Correct 92 ms 9872 KB Output is correct
7 Correct 112 ms 9880 KB Output is correct
8 Correct 105 ms 9820 KB Output is correct
9 Correct 103 ms 9812 KB Output is correct
10 Correct 90 ms 9816 KB Output is correct
11 Correct 95 ms 9660 KB Output is correct
12 Correct 135 ms 9660 KB Output is correct
13 Correct 115 ms 9640 KB Output is correct
14 Correct 121 ms 9636 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3152 KB Output is correct
2 Correct 16 ms 4052 KB Output is correct
3 Correct 20 ms 4808 KB Output is correct
4 Correct 64 ms 9636 KB Output is correct
5 Correct 64 ms 9840 KB Output is correct
6 Correct 65 ms 9636 KB Output is correct
7 Correct 104 ms 9600 KB Output is correct
8 Correct 63 ms 9628 KB Output is correct
9 Correct 61 ms 9656 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 10 ms 3152 KB Output is correct
3 Correct 73 ms 8364 KB Output is correct
4 Correct 109 ms 9836 KB Output is correct
5 Correct 128 ms 9848 KB Output is correct
6 Correct 114 ms 9928 KB Output is correct
7 Correct 72 ms 9776 KB Output is correct
8 Correct 130 ms 9760 KB Output is correct
9 Correct 118 ms 9876 KB Output is correct
10 Correct 124 ms 9776 KB Output is correct
11 Correct 133 ms 9636 KB Output is correct
12 Correct 134 ms 9640 KB Output is correct
13 Correct 138 ms 9656 KB Output is correct
14 Correct 108 ms 9636 KB Output is correct
15 Correct 76 ms 9772 KB Output is correct
16 Correct 70 ms 9784 KB Output is correct
17 Correct 97 ms 9756 KB Output is correct
18 Correct 115 ms 9676 KB Output is correct
19 Correct 98 ms 9828 KB Output is correct
20 Correct 76 ms 9652 KB Output is correct
21 Correct 86 ms 10112 KB Output is correct
22 Correct 77 ms 10116 KB Output is correct
23 Correct 104 ms 10040 KB Output is correct
24 Correct 84 ms 10156 KB Output is correct
25 Correct 87 ms 9696 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3296 KB Output is correct
2 Correct 11 ms 3280 KB Output is correct
3 Correct 129 ms 10128 KB Output is correct
4 Correct 145 ms 10552 KB Output is correct
5 Correct 145 ms 11284 KB Output is correct
6 Correct 137 ms 11316 KB Output is correct
7 Correct 194 ms 11232 KB Output is correct
8 Correct 160 ms 11236 KB Output is correct
9 Correct 94 ms 9052 KB Output is correct
10 Correct 121 ms 9456 KB Output is correct
11 Correct 170 ms 9472 KB Output is correct
12 Correct 158 ms 10680 KB Output is correct
13 Correct 144 ms 11240 KB Output is correct
14 Correct 163 ms 11080 KB Output is correct
15 Correct 154 ms 11264 KB Output is correct
16 Correct 125 ms 9864 KB Output is correct
17 Correct 111 ms 10276 KB Output is correct
18 Correct 93 ms 10248 KB Output is correct
19 Correct 94 ms 10228 KB Output is correct
20 Correct 99 ms 10312 KB Output is correct
21 Correct 164 ms 11124 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3280 KB Output is correct
2 Correct 12 ms 3328 KB Output is correct
3 Correct 102 ms 10216 KB Output is correct
4 Correct 161 ms 10308 KB Output is correct
5 Correct 130 ms 10500 KB Output is correct
6 Correct 153 ms 11364 KB Output is correct
7 Correct 112 ms 10160 KB Output is correct
8 Correct 117 ms 10408 KB Output is correct
9 Partially correct 127 ms 10528 KB Output is partially correct
10 Correct 155 ms 11276 KB Output is correct
11 Correct 178 ms 11256 KB Output is correct
12 Partially correct 156 ms 11224 KB Output is partially correct
13 Correct 100 ms 9516 KB Output is correct
14 Correct 173 ms 9460 KB Output is correct
15 Correct 130 ms 9460 KB Output is correct
16 Correct 148 ms 9680 KB Output is correct
17 Correct 111 ms 9480 KB Output is correct
18 Correct 146 ms 9412 KB Output is correct
19 Correct 164 ms 10680 KB Output is correct
20 Correct 136 ms 10964 KB Output is correct
21 Correct 170 ms 11080 KB Output is correct
22 Correct 137 ms 11164 KB Output is correct
23 Correct 193 ms 11076 KB Output is correct
24 Partially correct 188 ms 11092 KB Output is partially correct
25 Correct 143 ms 11156 KB Output is correct
26 Correct 139 ms 11116 KB Output is correct
27 Partially correct 113 ms 10316 KB Output is partially correct
28 Correct 121 ms 10200 KB Output is correct
29 Partially correct 103 ms 10356 KB Output is partially correct
30 Correct 95 ms 10248 KB Output is correct
31 Correct 117 ms 10224 KB Output is correct
32 Correct 85 ms 10296 KB Output is correct
33 Correct 111 ms 10368 KB Output is correct
34 Correct 93 ms 10216 KB Output is correct
35 Partially correct 115 ms 10240 KB Output is partially correct
36 Correct 118 ms 10164 KB Output is correct
37 Partially correct 105 ms 10388 KB Output is partially correct
38 Correct 140 ms 10296 KB Output is correct
39 Correct 128 ms 11200 KB Output is correct
40 Correct 185 ms 11124 KB Output is correct
41 Correct 155 ms 11128 KB Output is correct
42 Correct 170 ms 11148 KB Output is correct