oj.uz

Submission #117002

# Submission time Handle Problem Language Result Execution time Memory
117002 2019-06-14T12:06:00 Z dsjong Highway Tolls (IOI18_highway) C++14
12 / 100
 423 ms 262148 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
int NN;
long long AA,BB,CNT;
vector<int>adj[100005];
int dep[100005],par[100005];
int mp[100005];
vector<int>leaves;
void dfs(int i,int p){
	par[i]=p;
	for(int j:adj[i]){
		if(j==p) continue;
		dep[j]=dep[i]+1;
		dfs(j,i);
	}
}
bool pick[100005];
bool vis[100005];
vector<int>query;
bool check(int L,int R){
	query.clear();
	memset(pick,0,sizeof pick);
	memset(vis,0,sizeof vis);
	for(int i=L;i<=R;i++){
		int cur=leaves[i];
		while(!vis[cur]&&cur!=0){
			pick[mp[cur]]=true;
			vis[cur]=true;
			cur=par[cur];
		}
	}
	int cnt=0;
	for(int i=0;i<NN-1;i++){
		if(pick[i]){
			query.push_back(1);
			cnt++;
		}
		else query.push_back(0);
	}
	long long x=ask(query);
	if(x/BB>=CNT) return true;
	return false;
}
void find_pair(int n, std::vector<int> U, std::vector<int> V, int a, int b) {
	NN=n,AA=a,BB=b;
	for(int i=0;i<U.size();i++){
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
	}
	dep[0]=0;
	dfs(0,-1);
	for(int i=0;i<U.size();i++){
		if(par[U[i]]==V[i]) mp[U[i]]=i;
		else mp[V[i]]=i;
	}
	query.clear();
	for(int i=0;i<NN-1;i++){
		query.push_back(0);
	}
	CNT=ask(query)/AA;
	//cout<<CNT<<endl;
	for(int i=1;i<NN;i++){
		if(adj[i].size()==1) leaves.push_back(i);
	}
	
	/*for(int i:leaves) cout<<i<<" ";
	cout<<endl;*/
	int L=0,R=leaves.size()-1;
	while(L<R){
		//cout<<L<<" "<<R<<" ";
		if(R==L+1){
			if(check(L,L)) R=L;
			else L=R;
			break;
		}
		int M=(L+R)/2;
		if(check(L,M)) R=M;
		else L=M+1;
	}
	int ans=leaves[L];
	for(int i=0;i<dep[leaves[L]]-CNT;i++){
		ans=par[ans];
		//cout<<ans<<endl;
	}
	answer(ans,0);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<U.size();i++){
              ~^~~~~~~~~
highway.cpp:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<U.size();i++){
              ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2900 KB Output is correct
2 Correct 4 ms 2812 KB Output is correct
3 Correct 4 ms 2900 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 5 ms 2824 KB Output is correct
6 Correct 4 ms 2820 KB Output is correct
7 Correct 4 ms 2816 KB Output is correct
8 Correct 4 ms 2808 KB Output is correct
9 Correct 4 ms 2820 KB Output is correct
10 Correct 5 ms 2808 KB Output is correct
11 Correct 4 ms 2900 KB Output is correct
12 Correct 4 ms 2856 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2940 KB Output is correct
2 Correct 17 ms 3520 KB Output is correct
3 Correct 172 ms 9064 KB Output is correct
4 Correct 196 ms 9056 KB Output is correct
5 Correct 164 ms 9072 KB Output is correct
6 Correct 189 ms 9076 KB Output is correct
7 Correct 171 ms 9148 KB Output is correct
8 Correct 195 ms 9056 KB Output is correct
9 Correct 179 ms 9060 KB Output is correct
10 Correct 168 ms 9056 KB Output is correct
11 Correct 198 ms 9660 KB Output is correct
12 Correct 199 ms 10108 KB Output is correct
13 Correct 202 ms 9836 KB Output is correct
14 Correct 194 ms 9376 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 3920 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 5 ms 2936 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 Runtime error 423 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 371 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -