Submission #858964

#	Time	Username	Problem	Language	Result	Execution time	Memory
858964		qin	Highway Tolls (IOI18_highway)	C++17	18 / 100	137 ms	16592 KiB

highway

#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;
						}
						else 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: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31