oj.uz

Submission #835324

# Submission time Handle Problem Language Result Execution time Memory
835324 2023-08-23T13:05:45 Z arnold518 Highway Tolls (IOI18_highway) C++17
51 / 100
 216 ms 12004 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 dist1[MAXN+10], dist2[MAXN+10];
int P[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;
	}

	queue<int> Q;
	for(int i=1; i<=N; i++) dist1[i]=-1;
	Q.push(E[hi].first); dist1[E[hi].first]=0;
	while(!Q.empty())
	{
		int now=Q.front(); Q.pop();
		for(auto nxt : adj[now])
		{
			if(dist1[nxt]!=-1) continue;
			dist1[nxt]=dist1[now]+1;
			Q.push(nxt);
		}
	}

	for(int i=1; i<=N; i++) dist2[i]=-1;
	Q.push(E[hi].second); dist2[E[hi].second]=0;
	while(!Q.empty())
	{
		int now=Q.front(); Q.pop();
		for(auto nxt : adj[now])
		{
			if(dist2[nxt]!=-1) continue;
			dist2[nxt]=dist2[now]+1;
			Q.push(nxt);
		}
	}

	vector<pii> V1, V2;
	for(int i=1; i<=N; i++)
	{
		if(dist1[i]<dist2[i]) V1.push_back({dist1[i], i});
		if(dist1[i]>dist2[i]) V2.push_back({dist2[i], i});
	}

	sort(V1.begin(), V1.end());
	sort(V2.begin(), V2.end());

	for(int i=0; i<V1.size(); i++) P[V1[i].second]=i+1;
	for(int i=0; i<V2.size(); i++) P[V2[i].second]=-(i+1);

	//for(int i=1; i<=N; i++) printf("%d ", P[i]); printf("\n");

	lo=0, hi=V1.size();
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		for(int i=1; i<=M; i++)
		{
			auto [u, v]=E[i];
			if(P[u]==0 || P[v]==0) TT[i]=1;
			else if((P[u]>0)!=(P[v]>0)) TT[i]=1;
			else if(P[u]<0) TT[i]=0;
			else if(P[u]<=mid && P[v]<=mid) TT[i]=0;
			else TT[i]=1;
		}
		if(D*A+B-A!=query()) lo=mid;
		else hi=mid;
	}
	for(int i=1; i<=N; i++) if(P[i]==hi) S=i;
	//printf("!%d\n", hi);

	lo=0, hi=V2.size();
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		for(int i=1; i<=M; i++)
		{
			auto [u, v]=E[i];
			if(P[u]==0 || P[v]==0) TT[i]=1;
			else if((P[u]>0)!=(P[v]>0)) TT[i]=1;
			else if(P[u]>0) TT[i]=0;
			else if(-P[u]<=mid && -P[v]<=mid) TT[i]=0;
			else TT[i]=1;
		}
		if(D*A+B-A!=query()) lo=mid;
		else hi=mid;
	}
	for(int i=1; i<=N; i++) if(-P[i]==hi) T=i;
	//printf("!%d\n", 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:90:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for(int i=0; i<V1.size(); i++) P[V1[i].second]=i+1;
      |               ~^~~~~~~~~~
highway.cpp:91:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for(int i=0; i<V2.size(); i++) P[V2[i].second]=-(i+1);
      |               ~^~~~~~~~~~
highway.cpp:98:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |   int mid=lo+hi>>1;
      |           ~~^~~
highway.cpp:117:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  117 |   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 2 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 2 ms 2508 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 2532 KB Output is correct
2 Correct 12 ms 3280 KB Output is correct
3 Correct 113 ms 10540 KB Output is correct
4 Correct 108 ms 10500 KB Output is correct
5 Correct 106 ms 10504 KB Output is correct
6 Correct 101 ms 10480 KB Output is correct
7 Correct 119 ms 10500 KB Output is correct
8 Correct 141 ms 10520 KB Output is correct
9 Correct 106 ms 10504 KB Output is correct
10 Correct 142 ms 10468 KB Output is correct
11 Correct 154 ms 10672 KB Output is correct
12 Correct 110 ms 10448 KB Output is correct
13 Correct 102 ms 10384 KB Output is correct
14 Correct 103 ms 10448 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3260 KB Output is correct
2 Correct 24 ms 4208 KB Output is correct
3 Correct 34 ms 5044 KB Output is correct
4 Correct 79 ms 10420 KB Output is correct
5 Correct 89 ms 10372 KB Output is correct
6 Correct 103 ms 10584 KB Output is correct
7 Correct 82 ms 10384 KB Output is correct
8 Correct 121 ms 10348 KB Output is correct
9 Correct 101 ms 10360 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 26 ms 3264 KB Output is correct
3 Correct 90 ms 8884 KB Output is correct
4 Correct 98 ms 10464 KB Output is correct
5 Correct 104 ms 10512 KB Output is correct
6 Correct 92 ms 10608 KB Output is correct
7 Correct 120 ms 10592 KB Output is correct
8 Correct 111 ms 10500 KB Output is correct
9 Correct 116 ms 10576 KB Output is correct
10 Correct 119 ms 10484 KB Output is correct
11 Correct 112 ms 10384 KB Output is correct
12 Correct 146 ms 10428 KB Output is correct
13 Correct 123 ms 10560 KB Output is correct
14 Correct 165 ms 10540 KB Output is correct
15 Correct 96 ms 10640 KB Output is correct
16 Correct 113 ms 10532 KB Output is correct
17 Correct 142 ms 10444 KB Output is correct
18 Correct 122 ms 10500 KB Output is correct
19 Correct 116 ms 10600 KB Output is correct
20 Correct 108 ms 10496 KB Output is correct
21 Correct 91 ms 10972 KB Output is correct
22 Correct 126 ms 10976 KB Output is correct
23 Correct 108 ms 11244 KB Output is correct
24 Correct 137 ms 11216 KB Output is correct
25 Correct 105 ms 10524 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3404 KB Output is correct
2 Correct 11 ms 3460 KB Output is correct
3 Correct 131 ms 10836 KB Output is correct
4 Correct 146 ms 11320 KB Output is correct
5 Correct 216 ms 11948 KB Output is correct
6 Correct 204 ms 12004 KB Output is correct
7 Correct 154 ms 11896 KB Output is correct
8 Correct 185 ms 11868 KB Output is correct
9 Incorrect 154 ms 9348 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3288 KB Output is correct
2 Correct 15 ms 3468 KB Output is correct
3 Correct 144 ms 11068 KB Output is correct
4 Correct 161 ms 10976 KB Output is correct
5 Correct 172 ms 11320 KB Output is correct
6 Correct 193 ms 11872 KB Output is correct
7 Correct 114 ms 10992 KB Output is correct
8 Correct 168 ms 11024 KB Output is correct
9 Incorrect 175 ms 11280 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -