oj.uz

Submission #122903

# Submission time Handle Problem Language Result Execution time Memory
122903 2019-06-29T13:45:07 Z eriksuenderhauf Highway Tolls (IOI18_highway) C++11
51 / 100
 265 ms 10136 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 = 90050;
const double eps = 1e-9;
vii adj[MAXN], all;
int n, vis[MAXN], dp[MAXN];
ll dist;

int solve(int root) {
	mem(vis, 0);
	mem(dp, 0);
	deque<int> pq;
	pq.pb(root);
	vi edg;
	while (!pq.empty()) {
		int u = pq.front(); pq.pop_front();
		vis[u] = 1;
		for (pii nx: adj[u]) {
			if (vis[nx.fi]) continue;
			dp[nx.fi] = dp[u] + 1;
			pq.pb(nx.fi);
			edg.pb(nx.se);
		}
	}
	reverse(edg.begin(), edg.end());
	int lo = 0, hi = n-1, ans = 0;
	while (lo <= hi) {
		int mi = (lo+hi) / 2;
		vi tmp(n-1);
		for (int i = 0; i <= mi; i++)
			tmp[edg[i]] = 1;
		ll w = ask(tmp);
		if (w == dist)
			lo = mi + 1;
		else
			hi = mi - 1;
	}
	pii ret = all[edg[lo]];
	if (dp[ret.fi] < dp[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;
	for (int i = 0; i+1 < n; 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(n-1, 0));
	int s = solve(0);
	int t = solve(s);
	answer(s, t);
}

/*int main() {

    return 0;
}*/

Compilation message

highway.cpp: In function 'int solve(int)':
highway.cpp:59:24: warning: unused variable 'ans' [-Wunused-variable]
  int lo = 0, hi = n-1, ans = 0;
                        ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3120 KB Output is correct
2 Correct 5 ms 3044 KB Output is correct
3 Correct 5 ms 3064 KB Output is correct
4 Correct 5 ms 3196 KB Output is correct
5 Correct 5 ms 3192 KB Output is correct
6 Correct 5 ms 3064 KB Output is correct
7 Correct 5 ms 3112 KB Output is correct
8 Correct 4 ms 3088 KB Output is correct
9 Correct 6 ms 3192 KB Output is correct
10 Correct 5 ms 3112 KB Output is correct
11 Correct 5 ms 3088 KB Output is correct
12 Correct 5 ms 3112 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3112 KB Output is correct
2 Correct 17 ms 3760 KB Output is correct
3 Correct 210 ms 10004 KB Output is correct
4 Correct 217 ms 9980 KB Output is correct
5 Correct 212 ms 10028 KB Output is correct
6 Correct 207 ms 9984 KB Output is correct
7 Correct 252 ms 9968 KB Output is correct
8 Correct 224 ms 9964 KB Output is correct
9 Correct 197 ms 9968 KB Output is correct
10 Correct 220 ms 9976 KB Output is correct
11 Correct 235 ms 9432 KB Output is correct
12 Correct 223 ms 9440 KB Output is correct
13 Correct 265 ms 9412 KB Output is correct
14 Correct 229 ms 9408 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3704 KB Output is correct
2 Correct 40 ms 4496 KB Output is correct
3 Correct 62 ms 5224 KB Output is correct
4 Correct 165 ms 9604 KB Output is correct
5 Correct 182 ms 9500 KB Output is correct
6 Correct 179 ms 9532 KB Output is correct
7 Correct 167 ms 9420 KB Output is correct
8 Correct 165 ms 9440 KB Output is correct
9 Correct 176 ms 9544 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3192 KB Output is correct
2 Correct 27 ms 3868 KB Output is correct
3 Correct 181 ms 8528 KB Output is correct
4 Correct 219 ms 10056 KB Output is correct
5 Correct 221 ms 9972 KB Output is correct
6 Correct 211 ms 9976 KB Output is correct
7 Correct 200 ms 9984 KB Output is correct
8 Correct 224 ms 9964 KB Output is correct
9 Correct 224 ms 10000 KB Output is correct
10 Correct 220 ms 9964 KB Output is correct
11 Correct 226 ms 9428 KB Output is correct
12 Correct 216 ms 9408 KB Output is correct
13 Correct 224 ms 9504 KB Output is correct
14 Correct 230 ms 9408 KB Output is correct
15 Correct 203 ms 9984 KB Output is correct
16 Correct 211 ms 9996 KB Output is correct
17 Correct 224 ms 9420 KB Output is correct
18 Correct 232 ms 9528 KB Output is correct
19 Correct 215 ms 10056 KB Output is correct
20 Correct 218 ms 9436 KB Output is correct
21 Correct 183 ms 10136 KB Output is correct
22 Correct 197 ms 10120 KB Output is correct
23 Correct 187 ms 10124 KB Output is correct
24 Correct 185 ms 9616 KB Output is correct
25 Correct 201 ms 9524 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 3032 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 3040 KB Incorrect
2 Halted 0 ms 0 KB -