oj.uz

Submission #1026189

# Submission time Handle Problem Language Result Execution time Memory
1026189 2024-07-17T16:58:40 Z Lalic Highway Tolls (IOI18_highway) C++17
51 / 100
 225 ms 262144 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;

const int MAXN = 9e4+10;

int depth[MAXN], id[MAXN];
vector<pii> adj[MAXN];

void dfs(int ver, int prev){
	depth[ver]=depth[prev]+1;
	
	for(auto [u, v] : adj[ver]){
		if(u==prev) continue;
		id[u]=v;
		dfs(u, ver);
	}
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	int M=(int)U.size();
	
	for(int i=0;i<M;i++){
		adj[U[i]].pb({V[i], i});
		adj[V[i]].pb({U[i], i});
	}
	
	vector<int> w(M, 0);
	ll comp=ask(w);
	
	dfs(0, 0);
	
	vector<int> proc(N);
	iota(all(proc), 0);
	
	sort(all(proc), [&](int a, int b){ return depth[a]>depth[b]; });
	
	int low=0, high=N-2, best=-1;
	while(low<=high){
		int mid=(low+high)>>1;
		
		for(int i=0;i<=mid;i++) w[id[proc[i]]]=1;
		ll curr=ask(w);
		for(int i=0;i<=mid;i++) w[id[proc[i]]]=0;
		
		if(curr>comp){
			best=mid;
			high=mid-1;
		}
		else low=mid+1;
	}
	
	int s=proc[best];
	
	depth[s]=0;
	dfs(s, s);
	
	sort(all(proc), [&](int a, int b){ return depth[a]>depth[b]; });
	
	low=0; high=N-2; best=-1;
	while(low<=high){
		int mid=(low+high)>>1;
		
		for(int i=0;i<=mid;i++) w[id[proc[i]]]=1;
		ll curr=ask(w);
		for(int i=0;i<=mid;i++) w[id[proc[i]]]=0;
		
		if(curr>comp){
			best=mid;
			high=mid-1;
		}
		else low=mid+1;
	}
	
	int t=proc[best];
	
	answer(s, t);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 9 ms 3160 KB Output is correct
3 Correct 98 ms 8972 KB Output is correct
4 Correct 88 ms 8808 KB Output is correct
5 Correct 109 ms 8728 KB Output is correct
6 Correct 100 ms 8724 KB Output is correct
7 Correct 96 ms 8740 KB Output is correct
8 Correct 95 ms 8748 KB Output is correct
9 Correct 87 ms 8744 KB Output is correct
10 Correct 101 ms 8736 KB Output is correct
11 Correct 110 ms 9208 KB Output is correct
12 Correct 136 ms 9856 KB Output is correct
13 Correct 121 ms 9300 KB Output is correct
14 Correct 104 ms 9372 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3672 KB Output is correct
2 Correct 19 ms 4696 KB Output is correct
3 Correct 24 ms 5720 KB Output is correct
4 Correct 80 ms 12888 KB Output is correct
5 Correct 67 ms 12976 KB Output is correct
6 Correct 80 ms 12396 KB Output is correct
7 Correct 68 ms 12400 KB Output is correct
8 Correct 69 ms 12400 KB Output is correct
9 Correct 68 ms 12416 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 9 ms 3160 KB Output is correct
3 Correct 70 ms 7384 KB Output is correct
4 Correct 86 ms 8728 KB Output is correct
5 Correct 79 ms 8732 KB Output is correct
6 Correct 88 ms 8736 KB Output is correct
7 Correct 87 ms 8744 KB Output is correct
8 Correct 97 ms 8780 KB Output is correct
9 Correct 101 ms 8728 KB Output is correct
10 Correct 91 ms 8740 KB Output is correct
11 Correct 98 ms 9296 KB Output is correct
12 Correct 96 ms 9716 KB Output is correct
13 Correct 99 ms 9392 KB Output is correct
14 Correct 106 ms 9676 KB Output is correct
15 Correct 89 ms 8736 KB Output is correct
16 Correct 91 ms 8732 KB Output is correct
17 Correct 101 ms 9488 KB Output is correct
18 Correct 105 ms 9580 KB Output is correct
19 Correct 86 ms 8732 KB Output is correct
20 Correct 98 ms 10080 KB Output is correct
21 Correct 81 ms 8888 KB Output is correct
22 Correct 76 ms 8900 KB Output is correct
23 Correct 75 ms 8924 KB Output is correct
24 Correct 74 ms 9288 KB Output is correct
25 Correct 83 ms 12028 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 225 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 207 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -