oj.uz

Submission #821525

# Submission time Handle Problem Language Result Execution time Memory
821525 2023-08-11T11:08:08 Z Dan4Life Highway Tolls (IOI18_highway) C++17
12 / 100
 154 ms 262144 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int mxN = (int)2e5+10;
using ll = long long;
vector<pair<int,int>> adj[mxN];
vector<int> edges;
int n,m,dist = 0, dis[mxN];
void dfs(int s, int p){
	if(p!=-1) dis[s] = dis[p]+1;
	else dis[s] = 0;
	for(auto [u,i] : adj[s]){	
		if(u!=p){
			dfs(u,s);
			if(dis[u]==dist) edges.pb(i);
		}
	}
}

void find_pair(int N, vi u, vi v, int A, int B) {
	n = N; m = sz(u); vi w(m,0);
	for(int i = 0; i < m; i++){
		int a = u[i], b = v[i];
		adj[a].pb({b,i}); adj[b].pb({a,i});
	}
	ll toll = ask(w);
	dist = toll/A; dfs(0,-1);
	int l = 0, r = sz(edges)-1;
	while(l<r){
		int mid = (l+r)/2; fill(all(w),0);
		for(int i = 0; i <= mid; i++) w[edges[i]]=1;
		if(ask(w)!=toll) r=mid;
		else l=mid+1;
	}
	int ind = edges[l];
	if(dis[u[ind]]==dist) answer(0,u[ind]);
	else answer(0,v[ind]);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 9 ms 5592 KB Output is correct
3 Correct 107 ms 10604 KB Output is correct
4 Correct 64 ms 10588 KB Output is correct
5 Correct 77 ms 10588 KB Output is correct
6 Correct 91 ms 10520 KB Output is correct
7 Correct 63 ms 10548 KB Output is correct
8 Correct 92 ms 10568 KB Output is correct
9 Correct 99 ms 10488 KB Output is correct
10 Correct 76 ms 10584 KB Output is correct
11 Correct 62 ms 11628 KB Output is correct
12 Correct 54 ms 12348 KB Output is correct
13 Correct 80 ms 11788 KB Output is correct
14 Correct 75 ms 11080 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 6224 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 3 ms 4944 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 154 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 146 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -