oj.uz

Submission #799424

# Submission time Handle Problem Language Result Execution time Memory
799424 2023-07-31T14:07:53 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
90 / 100
 248 ms 42020 KB 
    #include "highway.h"
    #include <bits/stdc++.h>
     
    using namespace std;
     
    #define sep		' '
    #define debug(x)	cerr << #x << ": " << x << endl;
    #define all(x)		(x).begin(), (x).end()
     
    const int MAXN = 1e6 + 10;
     
    bool bad[MAXN];
    int askcnt = 0;
    int from[MAXN], to[MAXN], n, m, par[MAXN], mn;
    vector<int> adj[MAXN], dfs_order, fuck;
     
    inline int f(int ind, int v) {
    	return from[ind] ^ to[ind] ^ v;
    }
     
    void dfs(int v, int p) {
    	dfs_order.push_back(v);
    	for (int ind : adj[v]) {
    		int u = f(ind, v);
    		if (u == p) continue;
    		if (bad[u]) continue;
     
    		par[u] = ind;
    		dfs(u, v);
    	}
    }
     
     
    inline vector<int> seg(int l, int r) {
    	vector<int> ans;
    	for (int i = l; i <= r; i++)
    		ans.push_back(par[dfs_order[i]]);
     
    	return ans;
    }
     
    inline int get(vector<int> vec) {
    	askcnt++;
    	assert(askcnt <= 90);
    	vector<int> W(m);
    	for (int i = 0; i < m; i++) W[i] = 1;
    	for (int e : fuck)
    		W[e] = 0;
     
    	for (int e : vec)
    		W[e] = 1;
     
    	return ask(W);
    }
     
    inline int getp(vector<int> vec) {
    	askcnt++;
    	assert(askcnt <= 90);
    	vector<int> W(m);
    	for (int i = 0; i < m; i++) 
    		W[i] = 1;
    	for (int e : vec)
    		W[e] = 0;
     
    	return ask(W);
    }
     
    inline int get(int l, int r) {
    	return get(seg(l, r));
    }
     
    inline int getp(int l, int r) {
    	return getp(seg(l, r));
    }
     
    inline int find(int root) {
    	par[root] = -1;
    	dfs_order.clear();
     
    	dfs(root, root);
     
    	int l = 1, r = int(dfs_order.size()) - 1;
     
    	while (l < r) {
    		int mid = (l + r) >> 1;	
    		if (getp(1, mid) == mn) r = mid;
    		else l = mid + 1;
    	}
     
    	return dfs_order[l];
     
    }
     
    int dist[MAXN];
     
    const double Z = 0.5;
     
    int fucking_root;
     
    inline vector<int> random_spt() {
    	vector<int> ans;
    	queue<int> q;
     
    	int l = 0, r = n - 1;
    	while (l < r) {
    		int len = r - l;
    		int mid = l + Z * len;
    		mid = max(mid, l);
    		mid = min(mid, r - 1);
     
    		vector<int> W(m);
    	
    		for (int i = 0; i < m; i++)
    			if (from[i] <= mid || to[i] <= mid)
    				W[i] = 1;
     
    		if (ask(W) == mn) {
    			for (int i = l; i <= mid; i++) bad[i] = true;
    			l = mid + 1;
    		} else r = mid;
    	}
     
    	int v = l;
    	fucking_root = v;
     
    	memset(dist, 63, sizeof dist);
    	q.push(v);
    	dist[v] = 0;
     
    	while (!q.empty()) {
    		int v = q.front();
    		q.pop();
     
    		if (v < fucking_root) continue;
     
    		for (int ind : adj[v]) {
    			int u = f(ind, v);
    			if (u < fucking_root) continue;
    			if (dist[u] > dist[v] + 1) {
    				dist[u] = dist[v] + 1;
    				q.push(u);
    				ans.push_back(ind);
    			}
    		}
    	}
     
    	return ans;
    }
     
    void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    	m = U.size();
    	n = N;
     
    	for (int i = 0; i < m; i++) {
    		from[i] = U[i];
    		to[i] = V[i];
     
    		adj[from[i]].push_back(i);
    		adj[to[i]].push_back(i);
    	}
     
    	for (int i = 0; i < m; i++)
    		fuck.push_back(i);
     
    	mn = get({});
    	vector<int> tmp = random_spt();
     
    	fuck = tmp;
    	for (int i = 0; i < n; i++) adj[i].clear();
    	for (int ind : tmp) {
    		adj[from[ind]].push_back(ind);
    		adj[to[ind]].push_back(ind);
    	}
     
     
    	int v = find(fucking_root);
    	int u = find(v);
    	
    	cerr << u << sep << v << endl;
     
    	answer(u, v);
    }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27728 KB Output is correct
2 Correct 15 ms 27632 KB Output is correct
3 Correct 15 ms 27716 KB Output is correct
4 Correct 17 ms 27728 KB Output is correct
5 Correct 15 ms 27728 KB Output is correct
6 Correct 15 ms 27680 KB Output is correct
7 Correct 15 ms 27676 KB Output is correct
8 Correct 15 ms 27728 KB Output is correct
9 Correct 20 ms 27628 KB Output is correct
10 Correct 14 ms 27676 KB Output is correct
11 Correct 15 ms 27740 KB Output is correct
12 Correct 14 ms 27684 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27816 KB Output is correct
2 Correct 26 ms 28720 KB Output is correct
3 Correct 138 ms 35192 KB Output is correct
4 Correct 147 ms 34996 KB Output is correct
5 Correct 114 ms 35064 KB Output is correct
6 Correct 128 ms 35116 KB Output is correct
7 Correct 118 ms 35184 KB Output is correct
8 Correct 113 ms 35032 KB Output is correct
9 Correct 156 ms 35176 KB Output is correct
10 Correct 127 ms 35076 KB Output is correct
11 Correct 145 ms 36624 KB Output is correct
12 Correct 146 ms 37580 KB Output is correct
13 Correct 134 ms 36880 KB Output is correct
14 Correct 133 ms 36832 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 29216 KB Output is correct
2 Correct 39 ms 30572 KB Output is correct
3 Correct 36 ms 30224 KB Output is correct
4 Correct 121 ms 38676 KB Output is correct
5 Correct 106 ms 38752 KB Output is correct
6 Correct 127 ms 40368 KB Output is correct
7 Correct 124 ms 33936 KB Output is correct
8 Correct 87 ms 39556 KB Output is correct
9 Correct 101 ms 42020 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27728 KB Output is correct
2 Correct 25 ms 28472 KB Output is correct
3 Correct 94 ms 33372 KB Output is correct
4 Correct 109 ms 34224 KB Output is correct
5 Correct 116 ms 34728 KB Output is correct
6 Correct 111 ms 33820 KB Output is correct
7 Correct 138 ms 34524 KB Output is correct
8 Correct 113 ms 34360 KB Output is correct
9 Correct 126 ms 35068 KB Output is correct
10 Correct 141 ms 35028 KB Output is correct
11 Correct 155 ms 36124 KB Output is correct
12 Correct 145 ms 37504 KB Output is correct
13 Correct 151 ms 36888 KB Output is correct
14 Correct 121 ms 37396 KB Output is correct
15 Correct 127 ms 34968 KB Output is correct
16 Correct 115 ms 34208 KB Output is correct
17 Correct 148 ms 35928 KB Output is correct
18 Correct 129 ms 35256 KB Output is correct
19 Correct 82 ms 33652 KB Output is correct
20 Correct 102 ms 34132 KB Output is correct
21 Correct 112 ms 34988 KB Output is correct
22 Correct 114 ms 34632 KB Output is correct
23 Correct 101 ms 35416 KB Output is correct
24 Correct 102 ms 36076 KB Output is correct
25 Correct 159 ms 41244 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 28488 KB Output is correct
2 Correct 28 ms 28652 KB Output is correct
3 Correct 144 ms 35380 KB Output is correct
4 Correct 175 ms 35592 KB Output is correct
5 Correct 219 ms 36752 KB Output is correct
6 Correct 208 ms 36284 KB Output is correct
7 Correct 198 ms 36704 KB Output is correct
8 Correct 162 ms 36788 KB Output is correct
9 Correct 143 ms 33696 KB Output is correct
10 Correct 121 ms 34088 KB Output is correct
11 Correct 111 ms 33888 KB Output is correct
12 Correct 195 ms 35976 KB Output is correct
13 Correct 160 ms 36220 KB Output is correct
14 Correct 213 ms 36292 KB Output is correct
15 Correct 159 ms 36256 KB Output is correct
16 Correct 129 ms 35344 KB Output is correct
17 Correct 110 ms 35284 KB Output is correct
18 Correct 107 ms 35420 KB Output is correct
19 Correct 131 ms 35384 KB Output is correct
20 Correct 109 ms 35024 KB Output is correct
21 Correct 187 ms 36768 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28624 KB Output is correct
2 Correct 26 ms 28652 KB Output is correct
3 Correct 165 ms 35244 KB Output is correct
4 Partially correct 165 ms 35488 KB Output is partially correct
5 Correct 174 ms 35560 KB Output is correct
6 Partially correct 189 ms 36788 KB Output is partially correct
7 Correct 184 ms 35324 KB Output is correct
8 Partially correct 130 ms 35660 KB Output is partially correct
9 Partially correct 155 ms 35744 KB Output is partially correct
10 Correct 200 ms 36832 KB Output is correct
11 Correct 248 ms 36728 KB Output is correct
12 Correct 220 ms 36796 KB Output is correct
13 Correct 152 ms 34016 KB Output is correct
14 Correct 123 ms 34440 KB Output is correct
15 Correct 133 ms 34196 KB Output is correct
16 Correct 128 ms 34380 KB Output is correct
17 Correct 113 ms 33864 KB Output is correct
18 Correct 145 ms 34444 KB Output is correct
19 Correct 179 ms 35952 KB Output is correct
20 Correct 164 ms 36424 KB Output is correct
21 Correct 188 ms 36572 KB Output is correct
22 Correct 210 ms 36304 KB Output is correct
23 Partially correct 163 ms 36720 KB Output is partially correct
24 Partially correct 182 ms 36244 KB Output is partially correct
25 Correct 201 ms 35888 KB Output is correct
26 Correct 150 ms 36372 KB Output is correct
27 Correct 127 ms 35368 KB Output is correct
28 Correct 155 ms 35180 KB Output is correct
29 Correct 162 ms 35392 KB Output is correct
30 Partially correct 122 ms 35456 KB Output is partially correct
31 Correct 135 ms 35296 KB Output is correct
32 Correct 154 ms 35044 KB Output is correct
33 Correct 126 ms 35356 KB Output is correct
34 Correct 105 ms 35388 KB Output is correct
35 Correct 126 ms 35436 KB Output is correct
36 Correct 130 ms 35336 KB Output is correct
37 Correct 103 ms 35092 KB Output is correct
38 Partially correct 164 ms 35892 KB Output is partially correct
39 Partially correct 139 ms 37244 KB Output is partially correct
40 Correct 151 ms 37460 KB Output is correct
41 Partially correct 191 ms 36784 KB Output is partially correct
42 Correct 179 ms 36684 KB Output is correct