oj.uz

Submission #123659

# Submission time Handle Problem Language Result Execution time Memory
123659 2019-07-01T23:05:53 Z eriksuenderhauf Highway Tolls (IOI18_highway) C++11
51 / 100
 1500 ms 14096 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "highway.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 130050;
const double eps = 1e-9;
vii adj[MAXN], all;
int n, m, vis[MAXN], dp[2][MAXN];
ll dist;

int solve(int root, int idx) {
	deque<int> pq;
	pq.pb(root);
	vi edg, tmp(m, 1);
	while (!pq.empty()) {
		int u = pq.front(); pq.pop_front();
		for (pii nx: adj[u]) {
			if (dp[idx][nx.fi] != dp[idx][u] + 1) continue;
			tmp[nx.se] = 0;
			pq.pb(nx.fi);
			if (dp[idx][nx.fi] < dp[idx^1][nx.fi])
				edg.pb(nx.se);
		}
	}
	reverse(edg.begin(), edg.end());
	int lo = 0, hi = edg.size()-1, ans = -1;
	while (lo <= hi) {
		int mi = (lo+hi) / 2;
		vi cur;
		for (int i = 0; i <= mi; i++)
			tmp[edg[i]] = 1;
		ll w = ask(tmp);
		if (w == dist)
			lo = mi + 1;
		else {
			ans = mi;
			hi = mi - 1;
		}
		for (int i = 0; i <= mi; i++)
			tmp[edg[i]] = 0;
	}
	if (ans == -1) 
		return root;	
	pii ret = all[edg[ans]];
	if (dp[idx][ret.fi] < dp[idx][ret.se])
		swap(ret.fi, ret.se);
	return ret.fi;
}

void find_pair(int N, vi U, vi V, int a, int b) {
	n = N;
	m = U.size();
	for (int i = 0; i < m; i++) {
		adj[U[i]].pb(mp(V[i],i));
		adj[V[i]].pb(mp(U[i],i));
		all.pb(mp(U[i], V[i]));
	}
	dist = ask(vi(m, 0));
	int lo = 0, hi = m-1;
	while (lo <= hi) {
		int mi = (lo+hi) / 2;
		vi tmp(m);
		for (int i = 0; i <= mi; i++)
			tmp[i] = 1;
		ll w = ask(tmp);
		if (w == dist)
			lo = mi + 1;
		else
			hi = mi - 1;
	}
	int u = all[lo].fi, v = all[lo].se;
	mem(vis, 0);
	mem(dp, 0);
	deque<int> pq;
	vis[u] = 1; pq.pb(u);
	while (!pq.empty()) {
		int u2 = pq.front(); pq.pop_front();
		for (pii nx: adj[u2]) {
			if (vis[nx.fi]) continue;
			vis[nx.fi] = 1;
			dp[0][nx.fi] = dp[0][u2] + 1;
			pq.pb(nx.fi);
		}
	}
	mem(vis, 0);
	vis[v] = 1; pq.pb(v);
	while (!pq.empty()) {
		int u2 = pq.front(); pq.pop_front();
		for (pii nx: adj[u2]) {
			if (vis[nx.fi]) continue;
			vis[nx.fi] = 1;
			dp[1][nx.fi] = dp[1][u2] + 1;
			pq.pb(nx.fi);
		}
	}
	int s = solve(u, 0);
	int t = solve(v, 1);
	answer(s, t);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4852 KB Output is correct
2 Correct 28 ms 5588 KB Output is correct
3 Correct 235 ms 11724 KB Output is correct
4 Correct 210 ms 11716 KB Output is correct
5 Correct 217 ms 11724 KB Output is correct
6 Correct 201 ms 11792 KB Output is correct
7 Correct 203 ms 11736 KB Output is correct
8 Correct 181 ms 11716 KB Output is correct
9 Correct 184 ms 11728 KB Output is correct
10 Correct 230 ms 11800 KB Output is correct
11 Correct 243 ms 10792 KB Output is correct
12 Correct 253 ms 11108 KB Output is correct
13 Correct 245 ms 11164 KB Output is correct
14 Correct 256 ms 11144 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5520 KB Output is correct
2 Correct 45 ms 6232 KB Output is correct
3 Correct 47 ms 6972 KB Output is correct
4 Correct 167 ms 10768 KB Output is correct
5 Correct 163 ms 10804 KB Output is correct
6 Correct 173 ms 11188 KB Output is correct
7 Correct 169 ms 11180 KB Output is correct
8 Correct 179 ms 10808 KB Output is correct
9 Correct 189 ms 11104 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4940 KB Output is correct
2 Correct 27 ms 5588 KB Output is correct
3 Correct 168 ms 10376 KB Output is correct
4 Correct 225 ms 11728 KB Output is correct
5 Correct 228 ms 11732 KB Output is correct
6 Correct 202 ms 11732 KB Output is correct
7 Correct 222 ms 11736 KB Output is correct
8 Correct 206 ms 11740 KB Output is correct
9 Correct 206 ms 11804 KB Output is correct
10 Correct 239 ms 11724 KB Output is correct
11 Correct 233 ms 11184 KB Output is correct
12 Correct 228 ms 11120 KB Output is correct
13 Correct 243 ms 11116 KB Output is correct
14 Correct 278 ms 10908 KB Output is correct
15 Correct 223 ms 11844 KB Output is correct
16 Correct 227 ms 11752 KB Output is correct
17 Correct 263 ms 11136 KB Output is correct
18 Correct 259 ms 11152 KB Output is correct
19 Correct 233 ms 11736 KB Output is correct
20 Correct 250 ms 11156 KB Output is correct
21 Correct 183 ms 11892 KB Output is correct
22 Correct 194 ms 11880 KB Output is correct
23 Correct 214 ms 11576 KB Output is correct
24 Correct 201 ms 11392 KB Output is correct
25 Correct 241 ms 11276 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5648 KB Output is correct
2 Correct 35 ms 5744 KB Output is correct
3 Correct 259 ms 12296 KB Output is correct
4 Correct 300 ms 12804 KB Output is correct
5 Correct 334 ms 14096 KB Output is correct
6 Correct 333 ms 13968 KB Output is correct
7 Correct 336 ms 13896 KB Output is correct
8 Correct 329 ms 13520 KB Output is correct
9 Execution timed out 3065 ms 11792 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5680 KB Output is correct
2 Correct 34 ms 5796 KB Output is correct
3 Correct 285 ms 11860 KB Output is correct
4 Correct 288 ms 12212 KB Output is correct
5 Correct 287 ms 12748 KB Output is correct
6 Correct 340 ms 13512 KB Output is correct
7 Correct 254 ms 12940 KB Output is correct
8 Correct 307 ms 12600 KB Output is correct
9 Incorrect 281 ms 12332 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -