oj.uz

Submission #933828

# Submission time Handle Problem Language Result Execution time Memory
933828 2024-02-26T11:28:52 Z kim Highway Tolls (IOI18_highway) C++17
5 / 100
 195 ms 9552 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=0;
	{
		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=1,r=id;
	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 2748 KB Output is correct
3 Correct 1 ms 2740 KB Output is correct
4 Correct 1 ms 2744 KB Output is correct
5 Correct 1 ms 2748 KB Output is correct
6 Correct 1 ms 2744 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 2748 KB Output is correct
10 Correct 1 ms 2744 KB Output is correct
11 Correct 1 ms 2748 KB Output is correct
12 Correct 1 ms 2748 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 3300 KB Output is correct
3 Correct 123 ms 8344 KB Output is correct
4 Correct 93 ms 8100 KB Output is correct
5 Correct 152 ms 8320 KB Output is correct
6 Correct 83 ms 7868 KB Output is correct
7 Correct 94 ms 8132 KB Output is correct
8 Correct 100 ms 8124 KB Output is correct
9 Correct 88 ms 8104 KB Output is correct
10 Correct 97 ms 8108 KB Output is correct
11 Correct 100 ms 7956 KB Output is correct
12 Correct 146 ms 7956 KB Output is correct
13 Correct 92 ms 7976 KB Output is correct
14 Incorrect 104 ms 7548 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 14 ms 3340 KB Output is correct
2 Correct 27 ms 4060 KB Output is correct
3 Correct 24 ms 4896 KB Output is correct
4 Correct 61 ms 7740 KB Output is correct
5 Correct 58 ms 7744 KB Output is correct
6 Correct 65 ms 7748 KB Output is correct
7 Correct 70 ms 7724 KB Output is correct
8 Correct 64 ms 7500 KB Output is correct
9 Incorrect 60 ms 7496 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 2796 KB Output is correct
2 Correct 14 ms 3352 KB Output is correct
3 Correct 88 ms 6608 KB Output is correct
4 Correct 86 ms 8100 KB Output is correct
5 Correct 83 ms 8092 KB Output is correct
6 Correct 103 ms 8324 KB Output is correct
7 Correct 94 ms 7876 KB Output is correct
8 Correct 91 ms 7876 KB Output is correct
9 Incorrect 91 ms 7656 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 16 ms 3380 KB Output is correct
3 Correct 124 ms 8612 KB Output is correct
4 Correct 131 ms 8616 KB Output is correct
5 Correct 195 ms 9128 KB Output is correct
6 Correct 118 ms 9356 KB Output is correct
7 Correct 143 ms 9552 KB Output is correct
8 Incorrect 132 ms 9320 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 14 ms 3348 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -