oj.uz

Submission #933824

# Submission time Handle Problem Language Result Execution time Memory
933824 2024-02-26T11:27:01 Z kim Highway Tolls (IOI18_highway) C++17
5 / 100
 198 ms 10008 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

using ti3=tuple<int,int,int>;

vector<int> adj1[90005];
bitset<90005> vis;
int pre[90005];

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

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

Compilation message

highway.cpp: In function 'int play(int, std::vector<int>&, std::vector<int>&, 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:54:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i=0;i<U.size();++i){
      |              ~^~~~~~~~~
highway.cpp: In function 'int play(int, std::vector<int>&, std::vector<int>&, int)':
highway.cpp:51:1: warning: control reaches end of non-void function [-Wreturn-type]
   51 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2744 KB Output is correct
2 Correct 1 ms 2744 KB Output is correct
3 Correct 1 ms 2752 KB Output is correct
4 Correct 1 ms 2748 KB Output is correct
5 Correct 1 ms 2752 KB Output is correct
6 Correct 1 ms 2748 KB Output is correct
7 Correct 1 ms 2748 KB Output is correct
8 Correct 1 ms 2744 KB Output is correct
9 Correct 1 ms 2904 KB Output is correct
10 Correct 1 ms 2752 KB Output is correct
11 Correct 1 ms 2752 KB Output is correct
12 Correct 1 ms 2752 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2796 KB Output is correct
2 Correct 14 ms 3272 KB Output is correct
3 Correct 103 ms 8604 KB Output is correct
4 Correct 103 ms 7884 KB Output is correct
5 Correct 134 ms 8352 KB Output is correct
6 Correct 129 ms 7860 KB Output is correct
7 Correct 94 ms 8116 KB Output is correct
8 Correct 109 ms 8140 KB Output is correct
9 Correct 90 ms 8572 KB Output is correct
10 Correct 100 ms 8352 KB Output is correct
11 Correct 112 ms 7952 KB Output is correct
12 Correct 116 ms 8688 KB Output is correct
13 Correct 96 ms 7968 KB Output is correct
14 Incorrect 86 ms 7724 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 8 ms 3340 KB Output is correct
2 Correct 14 ms 3848 KB Output is correct
3 Correct 22 ms 4392 KB Output is correct
4 Correct 63 ms 7748 KB Output is correct
5 Correct 82 ms 7704 KB Output is correct
6 Correct 63 ms 7800 KB Output is correct
7 Correct 75 ms 7732 KB Output is correct
8 Correct 69 ms 7956 KB Output is correct
9 Incorrect 75 ms 7492 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 1 ms 2788 KB Output is correct
2 Correct 15 ms 3256 KB Output is correct
3 Correct 63 ms 6612 KB Output is correct
4 Correct 92 ms 8332 KB Output is correct
5 Correct 122 ms 7868 KB Output is correct
6 Correct 104 ms 8128 KB Output is correct
7 Correct 102 ms 7896 KB Output is correct
8 Correct 113 ms 8104 KB Output is correct
9 Incorrect 78 ms 7628 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 11 ms 3424 KB Output is correct
2 Correct 18 ms 3384 KB Output is correct
3 Correct 143 ms 8836 KB Output is correct
4 Correct 115 ms 8596 KB Output is correct
5 Correct 198 ms 9352 KB Output is correct
6 Correct 171 ms 10008 KB Output is correct
7 Correct 162 ms 9336 KB Output is correct
8 Incorrect 132 ms 9324 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 16 ms 3344 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -