oj.uz

Submission #933835

# Submission time Handle Problem Language Result Execution time Memory
933835 2024-02-26T11:37:06 Z kim Highway Tolls (IOI18_highway) C++17
5 / 100
 198 ms 11264 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
using pii=pair<int,int>;
#define f first
#define s second

int N,M;
vector<int> adj1[90005];
bool vis[90005];
int pre[90005],node[90005];
pii edge[130005];

vector<int> ans,tmp;
int dist;
int play(int u0){
	for(int i=0;i<N;++i) vis[i]=0;
	int id=0;
	{
		queue<int> q;
		q.emplace(u0);
		vis[u0]=1;
		while(q.size()){
			int u=q.front(); q.pop();
			pre[u]=++id;
			node[id]=u;
			for(auto &v:adj1[u]){
				if(vis[v]) continue;
				vis[v]=1;
				q.emplace(v);
			}
		}
	}
	int l=1,r=id;
	while(l<r){
		int mid=l+r>>1;
		for(int i=0;i<M;++i){
			auto &[u,v]=edge[i];
			if(pre[u]<=mid&&pre[v]<=mid) tmp[i]=0;
			else tmp[i]=1;
		}
		if(ask(tmp)==dist) r=mid;
		else l=mid+1;
	}
	ans.eb(node[l]);
	return node[l];
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	::N=N,M=U.size();
	for(int i=0;i<U.size();++i){
		adj1[U[i]].eb(V[i]);
		adj1[V[i]].eb(U[i]);
		edge[i]={U[i],V[i]};
		tmp.eb(0);
	}
	dist=ask(tmp);
	play(play(0));
	answer(ans[0],ans[1]);
}

Compilation message

highway.cpp: In function 'int play(int)':
highway.cpp:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   int mid=l+r>>1;
      |           ~^~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:52:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i=0;i<U.size();++i){
      |              ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4188 KB Output is correct
2 Correct 1 ms 4188 KB Output is correct
3 Correct 1 ms 4188 KB Output is correct
4 Correct 1 ms 4188 KB Output is correct
5 Correct 1 ms 4184 KB Output is correct
6 Correct 1 ms 4192 KB Output is correct
7 Correct 1 ms 4184 KB Output is correct
8 Correct 1 ms 4436 KB Output is correct
9 Correct 1 ms 4192 KB Output is correct
10 Correct 2 ms 4188 KB Output is correct
11 Correct 2 ms 4188 KB Output is correct
12 Correct 1 ms 4192 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4248 KB Output is correct
2 Correct 15 ms 4968 KB Output is correct
3 Correct 112 ms 10016 KB Output is correct
4 Correct 91 ms 9312 KB Output is correct
5 Correct 145 ms 9792 KB Output is correct
6 Correct 89 ms 9324 KB Output is correct
7 Correct 108 ms 9552 KB Output is correct
8 Correct 108 ms 9812 KB Output is correct
9 Correct 89 ms 9556 KB Output is correct
10 Correct 104 ms 9540 KB Output is correct
11 Correct 95 ms 9396 KB Output is correct
12 Correct 102 ms 9644 KB Output is correct
13 Correct 101 ms 9644 KB Output is correct
14 Incorrect 88 ms 9400 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4776 KB Output is correct
2 Correct 23 ms 5356 KB Output is correct
3 Correct 31 ms 5908 KB Output is correct
4 Correct 97 ms 9176 KB Output is correct
5 Correct 68 ms 9184 KB Output is correct
6 Correct 73 ms 8928 KB Output is correct
7 Correct 69 ms 9196 KB Output is correct
8 Correct 70 ms 9184 KB Output is correct
9 Incorrect 99 ms 9248 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 12 ms 4968 KB Output is correct
3 Correct 66 ms 8504 KB Output is correct
4 Correct 114 ms 9312 KB Output is correct
5 Correct 94 ms 9324 KB Output is correct
6 Correct 119 ms 9784 KB Output is correct
7 Correct 106 ms 9348 KB Output is correct
8 Correct 96 ms 9564 KB Output is correct
9 Incorrect 93 ms 9752 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4992 KB Output is correct
2 Correct 13 ms 5020 KB Output is correct
3 Correct 107 ms 9800 KB Output is correct
4 Correct 124 ms 10260 KB Output is correct
5 Correct 147 ms 11264 KB Output is correct
6 Correct 198 ms 10548 KB Output is correct
7 Correct 157 ms 10988 KB Output is correct
8 Incorrect 139 ms 10552 KB Output is incorrect: {s, t} is wrong.
9 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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