oj.uz

Submission #122901

# Submission time Handle Problem Language Result Execution time Memory
122901 2019-06-29T13:44:09 Z eriksuenderhauf Highway Tolls (IOI18_highway) C++11
51 / 100
 265 ms 10236 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());
	//for (int i = 0; i < edg.size(); i++) {
		//cerr << edg[i] << " " << all[edg[i]].fi << " " << all[edg[i]].se << "\n";
	//}
	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);
		//cerr << "ask: " << w << ": ";
		for (int i = 0; i < tmp.size(); i++)
			//cerr << tmp[i] << " ";
		//cerr << "\n";
		if (w == dist)
			lo = mi + 1;
		else
			hi = mi - 1;
	}
	pii ret = all[edg[lo]];
	//cerr << ret.fi << " " << ret.se << "\n";
	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);
	//cerr << s << " " << t << "\n";
	answer(s, t);
}

/*int main() {

    return 0;
}*/

Compilation message

highway.cpp: In function 'int solve(int)':
highway.cpp:70:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < tmp.size(); i++)
                   ~~^~~~~~~~~~~~
highway.cpp:62: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 3084 KB Output is correct
2 Correct 5 ms 3064 KB Output is correct
3 Correct 5 ms 3172 KB Output is correct
4 Correct 4 ms 3084 KB Output is correct
5 Correct 4 ms 3092 KB Output is correct
6 Correct 4 ms 3060 KB Output is correct
7 Correct 4 ms 3080 KB Output is correct
8 Correct 5 ms 3104 KB Output is correct
9 Correct 5 ms 3084 KB Output is correct
10 Correct 5 ms 3088 KB Output is correct
11 Correct 5 ms 3064 KB Output is correct
12 Correct 4 ms 3064 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3192 KB Output is correct
2 Correct 27 ms 3832 KB Output is correct
3 Correct 214 ms 9976 KB Output is correct
4 Correct 212 ms 9960 KB Output is correct
5 Correct 240 ms 10076 KB Output is correct
6 Correct 201 ms 9964 KB Output is correct
7 Correct 219 ms 9956 KB Output is correct
8 Correct 227 ms 10052 KB Output is correct
9 Correct 200 ms 10024 KB Output is correct
10 Correct 211 ms 10068 KB Output is correct
11 Correct 265 ms 9424 KB Output is correct
12 Correct 230 ms 9424 KB Output is correct
13 Correct 256 ms 9444 KB Output is correct
14 Correct 187 ms 9528 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3684 KB Output is correct
2 Correct 50 ms 4500 KB Output is correct
3 Correct 69 ms 5224 KB Output is correct
4 Correct 162 ms 9420 KB Output is correct
5 Correct 130 ms 9408 KB Output is correct
6 Correct 142 ms 9428 KB Output is correct
7 Correct 163 ms 9516 KB Output is correct
8 Correct 140 ms 9420 KB Output is correct
9 Correct 211 ms 9412 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3224 KB Output is correct
2 Correct 25 ms 3760 KB Output is correct
3 Correct 151 ms 8536 KB Output is correct
4 Correct 207 ms 10076 KB Output is correct
5 Correct 241 ms 9976 KB Output is correct
6 Correct 226 ms 10048 KB Output is correct
7 Correct 212 ms 9968 KB Output is correct
8 Correct 244 ms 10084 KB Output is correct
9 Correct 228 ms 9980 KB Output is correct
10 Correct 221 ms 9968 KB Output is correct
11 Correct 235 ms 9420 KB Output is correct
12 Correct 231 ms 9412 KB Output is correct
13 Correct 231 ms 9528 KB Output is correct
14 Correct 230 ms 9544 KB Output is correct
15 Correct 248 ms 10072 KB Output is correct
16 Correct 202 ms 10000 KB Output is correct
17 Correct 230 ms 9488 KB Output is correct
18 Correct 239 ms 9404 KB Output is correct
19 Correct 213 ms 9980 KB Output is correct
20 Correct 231 ms 9428 KB Output is correct
21 Correct 176 ms 10120 KB Output is correct
22 Correct 176 ms 10112 KB Output is correct
23 Correct 194 ms 10236 KB Output is correct
24 Correct 192 ms 9616 KB Output is correct
25 Correct 223 ms 9520 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 3064 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 3068 KB Incorrect
2 Halted 0 ms 0 KB -