oj.uz

Submission #120247

# Submission time Handle Problem Language Result Execution time Memory
120247 2019-06-24T05:11:01 Z 임유진(#2951) Highway Tolls (IOI18_highway) C++14
12 / 100
 183 ms 9540 KB 
#include "highway.h"
#include<vector>
#include<deque>

using namespace std;

#define MAXN 90000

typedef pair<int, int> pii;

vector<pii> e[MAXN];
pii par[MAXN];
int dep[MAXN];

void dfs(int x){
	for(auto a:e[x]) if(a.first!=par[x].first){
		par[a.first]=make_pair(x, a.second);
		dep[a.first]=dep[x]+1;
		dfs(a.first);
	}
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	int M=U.size();
	vector<int> w(M, 0);
	long long d;
	deque<int> T;

	if(M!=N-1) return;

	d=ask(w)/A;
	for(int i=0; i<M; i++){
		e[U[i]].push_back(make_pair(V[i], i));
		e[V[i]].push_back(make_pair(U[i], i));
	}
	dfs(0);
	
	//for(int i=0; i<N; i++) printf("%d ", par[i].second);
	//printf("\n");

	for(int i=0; i<N; i++) if(dep[i]==d) T.push_back(i);
	while(T.size()>1){
		//for(auto a:T) printf("%d ", a);
		//printf("\n");
		int t=T.size();
		for(int i=0; i<t/2; i++) w[par[T[i]].second]=1;
		//for(auto a:w) printf("%d ", a);
		//printf("\n");
		long long ar=ask(w);
		for(int i=0; i<t/2; i++) w[par[T[i]].second]=0;
		if(ar!=d*A) for(int i=t/2; i<t; i++) T.pop_back();
		else for(int i=0; i<t/2; i++) T.pop_front();
	}

	answer(0, T[0]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 4 ms 2424 KB Output is correct
3 Correct 4 ms 2512 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 4 ms 2428 KB Output is correct
8 Correct 3 ms 2508 KB Output is correct
9 Correct 4 ms 2424 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 3 ms 2428 KB Output is correct
12 Correct 3 ms 2344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 42 ms 3012 KB Output is correct
3 Correct 164 ms 8676 KB Output is correct
4 Correct 177 ms 8680 KB Output is correct
5 Correct 176 ms 8652 KB Output is correct
6 Correct 165 ms 8628 KB Output is correct
7 Correct 177 ms 8576 KB Output is correct
8 Correct 174 ms 8664 KB Output is correct
9 Correct 169 ms 8632 KB Output is correct
10 Correct 158 ms 8772 KB Output is correct
11 Correct 183 ms 8996 KB Output is correct
12 Correct 132 ms 9540 KB Output is correct
13 Correct 164 ms 9184 KB Output is correct
14 Correct 174 ms 8772 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 3496 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 4 ms 2424 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 21 ms 2600 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 2552 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -