oj.uz

답안 #120247

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
120247 2019-06-24T05:11:01 Z 임유진(#2951) 통행료 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 2552 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -