oj.uz

Submission #130541

# Submission time Handle Problem Language Result Execution time Memory
130541 2019-07-15T13:31:51 Z groeneprof Highway Tolls (IOI18_highway) C++14
12 / 100
 305 ms 262148 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct edge{
	int id, v;
};

int N, M, A, B;
vector<vector<edge> > graph;

void dfs(int u, int par, int id, int d, int dist, vector<int>& idlist, vector<int>& vlist){
	if(d == dist){
		idlist.push_back(id);
		vlist.push_back(u);
	}
	for(edge e : graph[u]) if(e.v!=par){
		dfs(e.v, u, e.id, d+1, dist, idlist, vlist);
	}
}

int findT(int S, int par, int dist, int id){
	vector<int> idlist, vlist;
	dfs(S, par, id, 0, dist, idlist, vlist);
	int L = 0, R = idlist.size();
	while(L!=R-1){
		int Mi = (L+R)/2;
		vector<signed> w(M, 0);
		for(int i = 0; i<Mi; i++){
			w[idlist[i]]=1;
		}
		if(ask(w)==dist*A){
			L = Mi;
		}
		else{
			R = Mi;
		}
	}
	return vlist[L];
}

void find_pair(signed _N, vector<signed> U, vector<signed> V, signed _A, signed _B) {
	N = _N;
	M = U.size();
	A = _A;
	B = _B;
	graph.resize(N);
	for(int i = 0; i<M; i++){
		graph[U[i]].push_back({i, V[i]});
		graph[V[i]].push_back({i, U[i]});
	}
	vector<signed> w(M, 0);
	int dist = ask(w)/A;
	answer(0, findT(0, 0, dist, -1));
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 320 KB Output is correct
2 Correct 2 ms 328 KB Output is correct
3 Correct 2 ms 328 KB Output is correct
4 Correct 2 ms 408 KB Output is correct
5 Correct 2 ms 296 KB Output is correct
6 Correct 2 ms 248 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 320 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 248 KB Output is correct
12 Correct 2 ms 248 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 18 ms 1284 KB Output is correct
3 Correct 182 ms 9576 KB Output is correct
4 Correct 170 ms 9484 KB Output is correct
5 Correct 177 ms 9480 KB Output is correct
6 Correct 168 ms 9272 KB Output is correct
7 Correct 178 ms 9384 KB Output is correct
8 Correct 183 ms 9512 KB Output is correct
9 Correct 160 ms 9244 KB Output is correct
10 Correct 183 ms 9604 KB Output is correct
11 Correct 185 ms 11552 KB Output is correct
12 Correct 166 ms 12704 KB Output is correct
13 Correct 200 ms 11756 KB Output is correct
14 Correct 190 ms 10848 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 2216 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 376 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 305 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 289 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -