oj.uz

Submission #582524

# Submission time Handle Problem Language Result Execution time Memory
582524 2022-06-24T03:38:37 Z 8e7 Highway Tolls (IOI18_highway) C++17
100 / 100
 323 ms 19676 KB 
#include "highway.h"
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<pii> adj[maxn], g[maxn];

ll mind;
vector<int> tmp;
int ord[maxn];
void dfs(int n, int par, int &cur, int lim) {
	ord[n] = ++cur;	
	if (cur > lim) return;
	for (auto [v, id]:adj[n]) {
		//debug(n, v);
		if (v != par && cur + 1 <= lim) {
			tmp[id] = 0;
			//debug("edge", n, v);
			dfs(v, n, cur, lim);
			if (cur > lim) return;
		} 
	}
}

int m, edges;

int type = 0;
int getind(int n, int root, vector<int> poss, vector<int> ed) {
	int low = 0, up = poss.size();
	tmp.resize(m, 0);	
	dfs(root, -1,low, 1<<30); 
	sort(poss.begin(), poss.end(), [&] (int x, int y){return ord[x] < ord[y];});
	pary(poss.begin(), poss.end());
	low = -1;
	while (low < up - 1) {
		int mid = (low + up) / 2;
		for (int i = 0;i < m;i++) tmp[i] = 1;
		for (int i:ed) tmp[i] = 0;
		int ini = 0;
		debug(poss[mid], ord[poss[mid]]);
		dfs(root, -1, ini, ord[poss[mid]]);
		pary(tmp.begin(), tmp.end());
		ll val = ask(tmp);
		if (val == mind) {
			up = mid;	
		} else {
			low = mid;
		}
	}
	debug(poss.size(), up, poss[up]);
	return poss[up];
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	int M = U.size();
	m = M;

	vector<int> ini(M, 0);
	mind = ask(ini);
	edges = mind / A;
	int low = 0, up = M;	
	while (low < up - 1) {
		int mid = (low + up) / 2;
		for (int i = 0;i < M;i++) {
			if (i < mid) ini[i] = 0;
			else ini[i] = 1;
		}
		if (ask(ini) == mind) {
			up = mid;
		} else {
			low = mid;
		}
	}

	for (int i = 0;i < M;i++) {
		g[U[i]].push_back({V[i], i});
		g[V[i]].push_back({U[i], i});
	}

	//debug(low, U[low], V[low]);
	vector<bool> vis(N, 0), from(N, 0);
	int root = U[low];	
	queue<int> que;
	que.push(root);
	que.push(V[low]);
	vis[root] = 1, vis[V[low]] = 1;
	from[V[low]] = 1;

	vector<int> su, sv, eu, ev;
	eu.push_back(low), ev.push_back(low);
	while (que.size()) {
		int cur = que.front();que.pop();
		vis[cur] = 1;
		if (from[cur]) sv.push_back(cur);
		else su.push_back(cur);

		for (auto [v, id]:g[cur]) {
			if (!vis[v]) {
				vis[v] = 1;
				from[v] = from[cur];
				adj[cur].push_back({v, id});
				adj[v].push_back({cur, id});
				if (from[cur]) ev.push_back(id);
				else eu.push_back(id);
				que.push(v);
			}
		}
	}

	//pary(su.begin(), su.end());
	//pary(sv.begin(), sv.end());
	int s = getind(N, root, su, ev);
	int t = getind(N, V[low], sv, eu);
	debug(s, t);
	answer(s, t);
}
/*
4 3 5 8 1 3
0 1
0 2
1 3
*/

Compilation message

highway.cpp: In function 'int getind(int, int, std::vector<int>, std::vector<int>)':
highway.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
highway.cpp:49:2: note: in expansion of macro 'pary'
   49 |  pary(poss.begin(), poss.end());
      |  ^~~~
highway.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
highway.cpp:56:3: note: in expansion of macro 'debug'
   56 |   debug(poss[mid], ord[poss[mid]]);
      |   ^~~~~
highway.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
highway.cpp:58:3: note: in expansion of macro 'pary'
   58 |   pary(tmp.begin(), tmp.end());
      |   ^~~~
highway.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
highway.cpp:66:2: note: in expansion of macro 'debug'
   66 |  debug(poss.size(), up, poss[up]);
      |  ^~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
highway.cpp:130:2: note: in expansion of macro 'debug'
  130 |  debug(s, t);
      |  ^~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5024 KB Output is correct
2 Correct 15 ms 6100 KB Output is correct
3 Correct 212 ms 15316 KB Output is correct
4 Correct 243 ms 15372 KB Output is correct
5 Correct 167 ms 15300 KB Output is correct
6 Correct 196 ms 15300 KB Output is correct
7 Correct 165 ms 15380 KB Output is correct
8 Correct 176 ms 15440 KB Output is correct
9 Correct 198 ms 15320 KB Output is correct
10 Correct 134 ms 15304 KB Output is correct
11 Correct 169 ms 15528 KB Output is correct
12 Correct 191 ms 16044 KB Output is correct
13 Correct 188 ms 15604 KB Output is correct
14 Correct 170 ms 15836 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6480 KB Output is correct
2 Correct 26 ms 7836 KB Output is correct
3 Correct 43 ms 9700 KB Output is correct
4 Correct 117 ms 17400 KB Output is correct
5 Correct 100 ms 17732 KB Output is correct
6 Correct 122 ms 19008 KB Output is correct
7 Correct 110 ms 19676 KB Output is correct
8 Correct 125 ms 18004 KB Output is correct
9 Correct 109 ms 18552 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5024 KB Output is correct
2 Correct 18 ms 6176 KB Output is correct
3 Correct 155 ms 13032 KB Output is correct
4 Correct 138 ms 15296 KB Output is correct
5 Correct 182 ms 15300 KB Output is correct
6 Correct 184 ms 15284 KB Output is correct
7 Correct 156 ms 15344 KB Output is correct
8 Correct 184 ms 15292 KB Output is correct
9 Correct 191 ms 15400 KB Output is correct
10 Correct 168 ms 15312 KB Output is correct
11 Correct 212 ms 15364 KB Output is correct
12 Correct 244 ms 16104 KB Output is correct
13 Correct 194 ms 15628 KB Output is correct
14 Correct 174 ms 15832 KB Output is correct
15 Correct 130 ms 15300 KB Output is correct
16 Correct 217 ms 15304 KB Output is correct
17 Correct 197 ms 15608 KB Output is correct
18 Correct 144 ms 15756 KB Output is correct
19 Correct 157 ms 15308 KB Output is correct
20 Correct 143 ms 16308 KB Output is correct
21 Correct 152 ms 16156 KB Output is correct
22 Correct 168 ms 16144 KB Output is correct
23 Correct 164 ms 15900 KB Output is correct
24 Correct 174 ms 16080 KB Output is correct
25 Correct 223 ms 19340 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6108 KB Output is correct
2 Correct 23 ms 6268 KB Output is correct
3 Correct 216 ms 15660 KB Output is correct
4 Correct 190 ms 16060 KB Output is correct
5 Correct 319 ms 17000 KB Output is correct
6 Correct 228 ms 17016 KB Output is correct
7 Correct 205 ms 16916 KB Output is correct
8 Correct 264 ms 16948 KB Output is correct
9 Correct 206 ms 12792 KB Output is correct
10 Correct 164 ms 12840 KB Output is correct
11 Correct 173 ms 13948 KB Output is correct
12 Correct 258 ms 15712 KB Output is correct
13 Correct 254 ms 16384 KB Output is correct
14 Correct 247 ms 16856 KB Output is correct
15 Correct 305 ms 16868 KB Output is correct
16 Correct 256 ms 13848 KB Output is correct
17 Correct 151 ms 16216 KB Output is correct
18 Correct 143 ms 16400 KB Output is correct
19 Correct 160 ms 16408 KB Output is correct
20 Correct 127 ms 16484 KB Output is correct
21 Correct 270 ms 17168 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6088 KB Output is correct
2 Correct 23 ms 6248 KB Output is correct
3 Correct 193 ms 15700 KB Output is correct
4 Correct 233 ms 15932 KB Output is correct
5 Correct 238 ms 16076 KB Output is correct
6 Correct 271 ms 16956 KB Output is correct
7 Correct 236 ms 15720 KB Output is correct
8 Correct 222 ms 15876 KB Output is correct
9 Correct 236 ms 16044 KB Output is correct
10 Correct 271 ms 16908 KB Output is correct
11 Correct 278 ms 16912 KB Output is correct
12 Correct 221 ms 16948 KB Output is correct
13 Correct 165 ms 14036 KB Output is correct
14 Correct 190 ms 12840 KB Output is correct
15 Correct 127 ms 14012 KB Output is correct
16 Correct 148 ms 12832 KB Output is correct
17 Correct 214 ms 13940 KB Output is correct
18 Correct 177 ms 12920 KB Output is correct
19 Correct 213 ms 15616 KB Output is correct
20 Correct 230 ms 16176 KB Output is correct
21 Correct 252 ms 16780 KB Output is correct
22 Correct 272 ms 16660 KB Output is correct
23 Correct 323 ms 16832 KB Output is correct
24 Correct 281 ms 16716 KB Output is correct
25 Correct 308 ms 16784 KB Output is correct
26 Correct 295 ms 16756 KB Output is correct
27 Correct 147 ms 16376 KB Output is correct
28 Correct 144 ms 16268 KB Output is correct
29 Correct 172 ms 16664 KB Output is correct
30 Correct 164 ms 16420 KB Output is correct
31 Correct 180 ms 16360 KB Output is correct
32 Correct 186 ms 16272 KB Output is correct
33 Correct 150 ms 16612 KB Output is correct
34 Correct 152 ms 16408 KB Output is correct
35 Correct 162 ms 16340 KB Output is correct
36 Correct 144 ms 16152 KB Output is correct
37 Correct 123 ms 16648 KB Output is correct
38 Correct 153 ms 16428 KB Output is correct
39 Correct 274 ms 17480 KB Output is correct
40 Correct 314 ms 17588 KB Output is correct
41 Correct 318 ms 17040 KB Output is correct
42 Correct 323 ms 17004 KB Output is correct