oj.uz

Submission #858961

# Submission time Handle Problem Language Result Execution time Memory
858961 2023-10-09T13:12:37 Z qin Highway Tolls (IOI18_highway) C++17
0 / 100
 10 ms 2284 KB 
#ifdef LOCAL
#else
#include "highway.h"
#endif
#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int inf = 2e09; ll infll = 2e18;
#ifdef LOCAL
ll ask(vector<int> w){ return 0; }
#else
#endif
ll main_dist;
struct st{
		int sz, u, i;
		st(){}
		st(int S, int U, int I) : sz(S), u(U), i(I) {}
		bool operator<(const st &x) const{ return sz > x.sz; }
};
struct cent{
		int l = 0;
		vector<int> vis, sz, d_src, w; vector<vector<pii>> g;
		void init(int n, vector<vector<pii>> &G){
				vis = vector<int>(), vis.resize(n);
				sz = vector<int>(), sz.resize(n);
				d_src = vector<int>(), d_src.resize(n);
				w.resize(n-1, 0);
				g = G;
		}
		void dfs(int x){
				vis[x] = l, sz[x] = 1;
				for(pii u : g[x]) if(vis[u.fi] < l) dfs(u.fi), sz[x] += sz[u.fi];
		}
		int find_cent(int x, int n){
				vis[x] = l; int ret = x;
				for(pii u : g[x]) if(vis[u.fi] < l && n/2 < sz[u.fi]) ret = find_cent(u.fi, n);
				return ret;
		}
		vector<st> tmp; //fi to rozmiar, se = indeks
		int deco(int x){
				tmp = vector<st>();
				++l; dfs(x);
				++l; int cnt = find_cent(x, sz[x]);
				++l; dfs(cnt);
				vis[cnt] = inf;
				int ret = cnt;
				bool not_here = 0;
				for(pii u : g[cnt]) if(vis[u.fi] != inf){
						if(d_src[u.fi] < d_src[cnt]){
								w[u.se] = 1;
								if(main_dist == ask(w)) w[u.se] = 0, ret = deco(u.fi), not_here = 1;
								w[u.se] = 0;
						}
						tmp.emplace_back(sz[u.fi], u.fi, u.se);
				}
				if(!not_here){
						sort(tmp.begin(), tmp.end());
						for(st u : tmp){
								w[u.i] = 1;
								if(main_dist < ask(w)){ w[u.i] = 0, ret = deco(u.u); break; }
								w[u.i] = 0;
						}
				}
				tmp = vector<st>();
				return ret;
		}
		void dfs_dist(int x, int dist){
				vis[x] = l, d_src[x] = dist;
				for(pii u : g[x]) if(vis[u.fi] < l) dfs_dist(u.fi, dist+1);
		}
		int start(int x){
				++l; dfs_dist(x, 0);
				return deco(x);
		}
} cent;
void find_pair(int n, vector<int> U, vector<int> V, int A, int B){
		vector<vector<pii>> g(n);
		int m = ssize(U);
		for(int i = 0; i < m; ++i) g[U[i]].emplace_back(V[i], i), g[V[i]].emplace_back(U[i], i);
		vector<int> w(m, 0);
		main_dist = ask(w);
		int l = 0, r = m-1, mid;
		while(l != r){
				mid = (l+r)>>1;
				for(int i = l; i <= mid; ++i) w[i] = 1;
				if(ask(w) != main_dist) r = mid;
				else l = mid+1;
				fill(w.begin(), w.end(), 0);
		}
		//znajdujemy s
		cent.init(n, g);
		cent.vis[V[l]] = inf;
		int s = cent.start(U[l]);
		cent.init(n, g);
		cent.vis[U[l]] = inf;
		int e = cent.start(V[l]);
		if(s > e) swap(s, e);
		#ifdef LOCAL
		#else
		answer(s, e);
		#endif
}
#ifdef LOCAL
int main(){
		int T = 1;
		for(++T; --T; ) ;//find_pair();
		return 0;
}
#endif

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 448 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 Correct 1 ms 516 KB Output is correct
2 Incorrect 10 ms 2084 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 2284 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 1 ms 516 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 10 ms 2064 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 2136 KB Incorrect
2 Halted 0 ms 0 KB -