oj.uz

Submission #123589

# Submission time Handle Problem Language Result Execution time Memory
123589 2019-07-01T17:37:12 Z eriksuenderhauf Highway Tolls (IOI18_highway) C++11
51 / 100
 271 ms 10572 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, 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);
	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);
			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;
	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 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:65: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 5 ms 3472 KB Output is correct
2 Correct 5 ms 3548 KB Output is correct
3 Correct 4 ms 3468 KB Output is correct
4 Correct 5 ms 3448 KB Output is correct
5 Correct 5 ms 3552 KB Output is correct
6 Correct 5 ms 3448 KB Output is correct
7 Correct 5 ms 3448 KB Output is correct
8 Correct 5 ms 3448 KB Output is correct
9 Correct 5 ms 3596 KB Output is correct
10 Correct 5 ms 3500 KB Output is correct
11 Correct 5 ms 3464 KB Output is correct
12 Correct 5 ms 3448 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3612 KB Output is correct
2 Correct 27 ms 4216 KB Output is correct
3 Correct 235 ms 10408 KB Output is correct
4 Correct 213 ms 10328 KB Output is correct
5 Correct 245 ms 10412 KB Output is correct
6 Correct 210 ms 10332 KB Output is correct
7 Correct 257 ms 10344 KB Output is correct
8 Correct 241 ms 10320 KB Output is correct
9 Correct 229 ms 10320 KB Output is correct
10 Correct 218 ms 10388 KB Output is correct
11 Correct 271 ms 9796 KB Output is correct
12 Correct 243 ms 9772 KB Output is correct
13 Correct 236 ms 9792 KB Output is correct
14 Correct 233 ms 9764 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4088 KB Output is correct
2 Correct 50 ms 4912 KB Output is correct
3 Correct 89 ms 5628 KB Output is correct
4 Correct 140 ms 9780 KB Output is correct
5 Correct 172 ms 9772 KB Output is correct
6 Correct 147 ms 9764 KB Output is correct
7 Correct 153 ms 9780 KB Output is correct
8 Correct 146 ms 9876 KB Output is correct
9 Correct 170 ms 9768 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3576 KB Output is correct
2 Correct 20 ms 4168 KB Output is correct
3 Correct 169 ms 8948 KB Output is correct
4 Correct 201 ms 10328 KB Output is correct
5 Correct 214 ms 10428 KB Output is correct
6 Correct 230 ms 10324 KB Output is correct
7 Correct 217 ms 10396 KB Output is correct
8 Correct 225 ms 10312 KB Output is correct
9 Correct 220 ms 10336 KB Output is correct
10 Correct 227 ms 10412 KB Output is correct
11 Correct 238 ms 9768 KB Output is correct
12 Correct 228 ms 9764 KB Output is correct
13 Correct 235 ms 9848 KB Output is correct
14 Correct 229 ms 9756 KB Output is correct
15 Correct 223 ms 10436 KB Output is correct
16 Correct 211 ms 10396 KB Output is correct
17 Correct 242 ms 9768 KB Output is correct
18 Correct 255 ms 9780 KB Output is correct
19 Correct 225 ms 10496 KB Output is correct
20 Correct 230 ms 9824 KB Output is correct
21 Correct 175 ms 10464 KB Output is correct
22 Correct 178 ms 10464 KB Output is correct
23 Correct 184 ms 10572 KB Output is correct
24 Correct 189 ms 10108 KB Output is correct
25 Correct 208 ms 9864 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 4392 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 4312 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -