oj.uz

Submission #104707

# Submission time Handle Problem Language Result Execution time Memory
104707 2019-04-09T01:22:54 Z turbat Highway Tolls (IOI18_highway) C++14
0 / 100
 33 ms 5624 KB 
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
using pii = pair <int, int>;
using vi = vector <int>;
#define N 200005
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define ll long long
int deep[N], cnt, flat[N], len,  curdeep;
vector <pii> edg[N];
pii parent[N];
bool vis[N];
void dfs(int u){
	vis[u] = 1;
	flat[cnt++] = u;
	for (pii v : edg[u])
		if (vis[v.F]){
			dfs(v.F);
			parent[v.F] = mp(u, v.S);			
		}
}
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
  	int M = U.size();
 	vi v(M);
 	ll maxdist, dist, mindist;
 	for (int i = 0;i < M;i++) v[i] = 1;
 	maxdist = ask(v);
 	for (int i = 0;i < M;i++) v[i] = 0;
 	for (int i = 0;i < M;i++){
 		edg[U[i]].pb(mp(V[i], i));
 		edg[V[i]].pb(mp(U[i], i));
 	}
 	dfs(1);
 	int l = 1, r = n - 1, mid;
 	while (l != r){
 		mid = (l + r) / 2;
 		for (int i = l;i <= mid;i++)
 			v[parent[flat[i]].S] = 1;
 		dist = ask(v);
 		if (dist < maxdist) l = mid + 1;
 		else {
 			r = mid;
	 		for (int i = l;i <= mid;i++)
	 			v[parent[flat[i]].S] = 0;
 		}
 	}
 	for (int i = 0;i < M;i++) v[i] = 0;
 	int s = flat[l];
 	r = l;
 	l = 2;
 	while (l != r){
 		mid = (l + r + 1) / 2;
 		for (int i = mid;i <= r;i++)
 			v[parent[flat[i]].S] = 1;
 		if (dist < maxdist)	r = mid - 1;
 		else{
 			l = mid;
	 		for (int i = mid;i <= r;i++)
	 			v[parent[flat[i]].S] = 0;
 		}
 	}
 	int t = parent[flat[l]].F;
 	answer(s, t);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:28:21: warning: unused variable 'mindist' [-Wunused-variable]
   ll maxdist, dist, mindist;
                     ^~~~~~~
highway.cpp:58:4: warning: 'dist' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if (dist < maxdist) r = mid - 1;
    ^~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 5624 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 33 ms 5624 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -