oj.uz

Submission #123636

# Submission time Handle Problem Language Result Execution time Memory
123636 2019-07-01T20:36:02 Z eriksuenderhauf Highway Tolls (IOI18_highway) C++11
51 / 100
 322 ms 13960 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[MAXN], mrk[MAXN];
ll dist;

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

Compilation message

highway.cpp: In function 'int solve(int)':
highway.cpp:68: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 6 ms 4796 KB Output is correct
2 Correct 6 ms 4792 KB Output is correct
3 Correct 6 ms 4792 KB Output is correct
4 Correct 6 ms 4804 KB Output is correct
5 Correct 6 ms 4856 KB Output is correct
6 Correct 6 ms 4792 KB Output is correct
7 Correct 6 ms 4860 KB Output is correct
8 Correct 6 ms 4856 KB Output is correct
9 Correct 6 ms 4856 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 7 ms 4856 KB Output is correct
12 Correct 6 ms 4856 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4884 KB Output is correct
2 Correct 29 ms 5544 KB Output is correct
3 Correct 241 ms 11736 KB Output is correct
4 Correct 224 ms 11820 KB Output is correct
5 Correct 253 ms 11744 KB Output is correct
6 Correct 204 ms 11744 KB Output is correct
7 Correct 193 ms 11828 KB Output is correct
8 Correct 258 ms 11740 KB Output is correct
9 Correct 238 ms 11716 KB Output is correct
10 Correct 224 ms 11752 KB Output is correct
11 Correct 249 ms 11184 KB Output is correct
12 Correct 253 ms 11184 KB Output is correct
13 Correct 247 ms 11184 KB Output is correct
14 Correct 236 ms 11188 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5496 KB Output is correct
2 Correct 45 ms 6320 KB Output is correct
3 Correct 91 ms 7032 KB Output is correct
4 Correct 168 ms 11184 KB Output is correct
5 Correct 182 ms 11180 KB Output is correct
6 Correct 171 ms 11204 KB Output is correct
7 Correct 191 ms 11196 KB Output is correct
8 Correct 182 ms 11180 KB Output is correct
9 Correct 191 ms 11180 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 28 ms 5596 KB Output is correct
3 Correct 187 ms 10392 KB Output is correct
4 Correct 243 ms 11752 KB Output is correct
5 Correct 240 ms 11748 KB Output is correct
6 Correct 230 ms 11808 KB Output is correct
7 Correct 239 ms 11788 KB Output is correct
8 Correct 221 ms 11740 KB Output is correct
9 Correct 241 ms 11764 KB Output is correct
10 Correct 234 ms 11800 KB Output is correct
11 Correct 232 ms 11184 KB Output is correct
12 Correct 232 ms 11176 KB Output is correct
13 Correct 234 ms 11196 KB Output is correct
14 Correct 250 ms 11204 KB Output is correct
15 Correct 231 ms 11744 KB Output is correct
16 Correct 249 ms 11760 KB Output is correct
17 Correct 235 ms 11184 KB Output is correct
18 Correct 231 ms 11280 KB Output is correct
19 Correct 239 ms 11776 KB Output is correct
20 Correct 241 ms 11284 KB Output is correct
21 Correct 195 ms 12004 KB Output is correct
22 Correct 195 ms 11892 KB Output is correct
23 Correct 211 ms 11888 KB Output is correct
24 Correct 193 ms 11376 KB Output is correct
25 Correct 238 ms 11260 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5716 KB Output is correct
2 Correct 32 ms 5880 KB Output is correct
3 Correct 253 ms 12216 KB Output is correct
4 Correct 267 ms 12768 KB Output is correct
5 Correct 302 ms 13960 KB Output is correct
6 Incorrect 322 ms 13940 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5712 KB Output is correct
2 Correct 32 ms 5760 KB Output is correct
3 Partially correct 277 ms 12328 KB Output is partially correct
4 Partially correct 289 ms 12536 KB Output is partially correct
5 Incorrect 252 ms 12744 KB Output isn't correct
6 Halted 0 ms 0 KB -