oj.uz

Submission #933809

# Submission time Handle Problem Language Result Execution time Memory
933809 2024-02-26T10:59:31 Z kim Highway Tolls (IOI18_highway) C++17
5 / 100
 169 ms 12960 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],adj2[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){
	for(int i=0;i<n;++i) adj2[i].clear();
	vis=0;
	int m=U.size();
	{
		queue<int> q;
		q.emplace(u0);
		vis[u0]=1;
		while(q.size()){
			int u=q.front(); q.pop();
			for(auto &v:adj1[u]){
				if(vis[v]) continue;
				vis[v]=1;
				q.emplace(v);
				adj2[u].eb(v);
			}
		}
	}
	{
		stack<pii> st;
		st.emplace(u0,u0);
		int id=-1;
		while(st.size()){
			auto [u,p]=st.top(); st.pop();
			pre[u]=++id;
			for(auto &v:adj2[u]){
				if(v!=p) st.emplace(v,u);
			}
		}
	}
	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;
	}
	cerr<<pre[0]<<" "<<pre[1]<<" "<<pre[2]<<" "<<pre[3]<<'\n';
	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],0);
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4864 KB Output is correct
2 Correct 1 ms 4864 KB Output is correct
3 Correct 1 ms 4872 KB Output is correct
4 Correct 1 ms 4952 KB Output is correct
5 Correct 1 ms 4868 KB Output is correct
6 Correct 1 ms 4868 KB Output is correct
7 Correct 1 ms 4868 KB Output is correct
8 Correct 2 ms 4868 KB Output is correct
9 Correct 1 ms 4864 KB Output is correct
10 Correct 1 ms 4868 KB Output is correct
11 Correct 1 ms 4868 KB Output is correct
12 Correct 1 ms 4872 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4916 KB Output is correct
2 Correct 11 ms 5592 KB Output is correct
3 Correct 96 ms 11444 KB Output is correct
4 Correct 135 ms 11936 KB Output is correct
5 Correct 124 ms 11452 KB Output is correct
6 Correct 169 ms 12332 KB Output is correct
7 Correct 103 ms 11460 KB Output is correct
8 Correct 119 ms 11436 KB Output is correct
9 Correct 117 ms 11852 KB Output is correct
10 Correct 152 ms 11420 KB Output is correct
11 Correct 94 ms 12696 KB Output is correct
12 Correct 136 ms 12680 KB Output is correct
13 Correct 128 ms 12960 KB Output is correct
14 Incorrect 131 ms 12736 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 Incorrect 9 ms 5732 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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