oj.uz

Submission #835055

# Submission time Handle Problem Language Result Execution time Memory
835055 2023-08-23T07:14:01 Z arnold518 Highway Tolls (IOI18_highway) C++17
90 / 100
 212 ms 11316 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;
		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 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 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 1 ms 2384 KB Output is correct
11 Correct 1 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 2512 KB Output is correct
2 Correct 8 ms 3272 KB Output is correct
3 Correct 123 ms 9828 KB Output is correct
4 Correct 113 ms 9856 KB Output is correct
5 Correct 116 ms 9768 KB Output is correct
6 Correct 96 ms 9824 KB Output is correct
7 Correct 113 ms 9916 KB Output is correct
8 Correct 125 ms 9824 KB Output is correct
9 Correct 109 ms 9820 KB Output is correct
10 Correct 115 ms 9804 KB Output is correct
11 Correct 111 ms 9664 KB Output is correct
12 Correct 124 ms 9696 KB Output is correct
13 Correct 113 ms 9760 KB Output is correct
14 Correct 113 ms 9660 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3152 KB Output is correct
2 Correct 15 ms 4048 KB Output is correct
3 Correct 42 ms 4796 KB Output is correct
4 Correct 79 ms 9680 KB Output is correct
5 Correct 78 ms 9648 KB Output is correct
6 Correct 80 ms 9636 KB Output is correct
7 Correct 89 ms 9648 KB Output is correct
8 Correct 79 ms 9700 KB Output is correct
9 Correct 81 ms 9796 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2560 KB Output is correct
2 Correct 10 ms 3152 KB Output is correct
3 Correct 78 ms 8548 KB Output is correct
4 Correct 97 ms 9772 KB Output is correct
5 Correct 97 ms 9832 KB Output is correct
6 Correct 100 ms 9784 KB Output is correct
7 Correct 94 ms 9784 KB Output is correct
8 Correct 94 ms 9760 KB Output is correct
9 Correct 122 ms 9824 KB Output is correct
10 Correct 118 ms 9768 KB Output is correct
11 Correct 125 ms 9656 KB Output is correct
12 Correct 124 ms 9700 KB Output is correct
13 Correct 133 ms 9652 KB Output is correct
14 Correct 116 ms 9644 KB Output is correct
15 Correct 100 ms 9804 KB Output is correct
16 Correct 103 ms 9780 KB Output is correct
17 Correct 113 ms 9644 KB Output is correct
18 Correct 107 ms 9632 KB Output is correct
19 Correct 111 ms 10032 KB Output is correct
20 Correct 96 ms 9684 KB Output is correct
21 Correct 89 ms 10216 KB Output is correct
22 Correct 84 ms 10180 KB Output is correct
23 Correct 103 ms 10048 KB Output is correct
24 Correct 90 ms 9992 KB Output is correct
25 Correct 105 ms 9792 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3280 KB Output is correct
2 Correct 12 ms 3280 KB Output is correct
3 Correct 130 ms 10136 KB Output is correct
4 Correct 155 ms 10548 KB Output is correct
5 Correct 155 ms 11252 KB Output is correct
6 Correct 140 ms 11224 KB Output is correct
7 Correct 147 ms 11232 KB Output is correct
8 Correct 138 ms 11280 KB Output is correct
9 Correct 122 ms 9148 KB Output is correct
10 Correct 128 ms 9380 KB Output is correct
11 Correct 125 ms 9568 KB Output is correct
12 Correct 180 ms 10708 KB Output is correct
13 Correct 181 ms 10936 KB Output is correct
14 Correct 157 ms 11088 KB Output is correct
15 Correct 147 ms 11092 KB Output is correct
16 Correct 139 ms 9912 KB Output is correct
17 Correct 105 ms 10260 KB Output is correct
18 Correct 106 ms 10360 KB Output is correct
19 Correct 108 ms 10220 KB Output is correct
20 Correct 106 ms 10288 KB Output is correct
21 Correct 167 ms 11164 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3280 KB Output is correct
2 Correct 11 ms 3272 KB Output is correct
3 Correct 124 ms 10220 KB Output is correct
4 Correct 136 ms 10348 KB Output is correct
5 Correct 163 ms 10592 KB Output is correct
6 Partially correct 171 ms 11312 KB Output is partially correct
7 Partially correct 127 ms 10300 KB Output is partially correct
8 Partially correct 139 ms 10288 KB Output is partially correct
9 Partially correct 147 ms 10560 KB Output is partially correct
10 Partially correct 149 ms 11316 KB Output is partially correct
11 Partially correct 182 ms 11224 KB Output is partially correct
12 Partially correct 173 ms 11232 KB Output is partially correct
13 Correct 136 ms 9536 KB Output is correct
14 Correct 150 ms 9400 KB Output is correct
15 Correct 132 ms 9476 KB Output is correct
16 Correct 134 ms 9472 KB Output is correct
17 Correct 134 ms 9516 KB Output is correct
18 Correct 121 ms 9484 KB Output is correct
19 Correct 155 ms 10660 KB Output is correct
20 Correct 144 ms 10864 KB Output is correct
21 Partially correct 153 ms 11124 KB Output is partially correct
22 Partially correct 160 ms 11096 KB Output is partially correct
23 Partially correct 150 ms 11164 KB Output is partially correct
24 Partially correct 206 ms 11100 KB Output is partially correct
25 Partially correct 180 ms 11260 KB Output is partially correct
26 Correct 151 ms 11112 KB Output is correct
27 Partially correct 109 ms 10332 KB Output is partially correct
28 Correct 115 ms 10184 KB Output is correct
29 Partially correct 102 ms 10372 KB Output is partially correct
30 Partially correct 114 ms 10296 KB Output is partially correct
31 Correct 114 ms 10232 KB Output is correct
32 Correct 118 ms 10164 KB Output is correct
33 Correct 104 ms 10364 KB Output is correct
34 Correct 93 ms 10216 KB Output is correct
35 Partially correct 105 ms 10232 KB Output is partially correct
36 Correct 94 ms 10172 KB Output is correct
37 Partially correct 124 ms 10340 KB Output is partially correct
38 Correct 117 ms 10400 KB Output is correct
39 Partially correct 212 ms 11112 KB Output is partially correct
40 Partially correct 162 ms 11100 KB Output is partially correct
41 Partially correct 200 ms 11136 KB Output is partially correct
42 Partially correct 142 ms 11120 KB Output is partially correct