| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 244180 | crossing0ver | Highway Tolls (IOI18_highway) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define ll long long
#define fi first
#define se second
//#define local
#ifndef local
#include "highway.h"
#endif
using namespace std;
const int N = 1e5+5;
int n,m;
vi adj[N];
int sz[N],P[N],bad[N],vis[N],a,b,GraphSize;
map<pii,int> id;
ll dis;
vi WW;
pii mn = {INT_MAX,0},ans;
#ifdef local
int ask(vi v) {
if (v.size() != m) {
cout <<"VECTOR SIZE ERROR:404";
exit(0);
}
int ans =0;
if (v[2] == 0 ) ans += a;
else ans += b;
/*for (int i = 0; i < m;i++) {
if (v[i]== 0) ans += a;
else ans += b;
}*/
return ans;
}
#endif
vector<int> vec,V,U;
int flag;
int sizeofcomp(int v,int p) {
int s = 1;
for (int i : adj[v]) {
if (i == p || bad[i]) continue;
s += sizeofcomp(i,v);
}
return s;
}
void dfs(int v,int p) {
int mx_child = 0;
sz[v] = 0;
P[v] = p;
if (flag==1) {
vec.pb(id[{v,p}]);
}
for (int i : adj[v]) {
if (i == p || bad[i]) continue;
dfs(i,v);
mx_child = max(mx_child,sz[i] + 1);
sz[v] += sz[i] + 1;
}
int e = max(mx_child,GraphSize - sz[v] - 1);
mn = min(mn, {e,v});
}
void find(vector<int>& v,int root) {
int l = 0, r = v.size() - 1;
while (l != r) {
fill(WW.begin(),WW.end(),0);
int m = (l + r)/2;
for (int i = l; i <= m;i++)
WW[id[{root,v[i]}]] = 1;
if (ask(WW) == dis) { l = m + 1;}
else {
r = m;
}
}
vi g;
for (int i = l;i < v.size(); i++) {
g.pb(v[i]);
}
v = g;
}
void find_k(int v,int p,int depth,int k) {
if (depth == k) vec.pb(v);
for (int i : adj[v]) {
if (bad[i] || i == p) continue;
find_k(i,v,depth+1,k);
}
}
int findWithParent(vector <int> v) {
int l = 0, r = v.size() - 1;
while (l != r) {
fill(WW.begin(),WW.end(),0);
int m = (l + r)/2;
for (int i = l; i <= m; i++) {
WW[id[{v[i],P[v[i]]}]] = 1;
}
if (ask(WW) == dis) {
l = m + 1;
}
else r = m;
}
return v[r];
}
void process(int root) {
GraphSize = sizeofcomp(root,-1);
if (GraphSize == 2) {
ans.fi = root;
ans.se = adj[root][0];
return;
}
flag = 0;
vi e;
fill(WW.begin(),WW.end(),0);
for (int i : adj[root]) {
if (bad[i]) continue;
WW[id[{root,i}]] = 1;
e.pb(i);
}
ll d = ask(WW);
if (d > dis + b - a) {
find(e,root);
int x = e[0];
swap(e[0],e.back());
e.pop_back();
find(e,root);
int y = e[0];
e.clear();
adj[root].clear();
adj[root].pb(x);
adj[root].pb(y);
vec.clear();
flag = 1;
dfs(x,root);
fill(WW.begin(),WW.end(),0);
for (int i : vec) WW[i] = 1;
ll d = ask(WW);
int D = (d - dis)/(b-a);
vec.clear();
find_k(x,root,1,D);
x = findWithParent(vec);
D = dis/a - D;
vec.clear();
find_k(y,root,1,D);
y = findWithParent(vec);
ans = {x,y};
return;
}
else {
flag = 1;
vector<vector<int> > v;
vec.clear();
for (int i : e) {
dfs(i,root);
v.pb(vec);
vec.clear();
}
flag = 0;
int l = 0, r = v.size() - 1;
while (v.size() != 1) {
int m = v.size()/2;
fill(WW.begin(),WW.end(),0);
for (int i = m; i < v.size(); i++) {
for (int x : v[i]) WW[x] = 1;
}
if (ask(WW) == dis) {
while(v.size() != m) v.pop_back();
}
else {
vector<vector<int> > g = v;
v.clear();
for (int i = m; i < g.size(); i++) v.pb(g[i]);
g.clear();
}
}
int x = V[v[0][0]]^U[v[0][0]]^root;
adj[root].clear();
adj[root].pb(x);
mn = {INT_MAX,0};
vec.clear();
flag = 0;
GraphSize = sizeofcomp(root,-1);
dfs(root,-1);
root = mn.se;
/* if (adj[root].size() == 1 && GraphSize == 3) {
cout << adj[2][1];
}*/
process(root);
}
}
pii solve(vi U,vi V) {
GraphSize = n;
dis = ask(WW);
sizeofcomp(0,-1);
dfs(0,-1);
int root = mn.se;
process(root);
return ans;
}
pair<int,int> find_pair(int N1, vi U1, vi V1,int a1,int b1) {
U = U1; V = V1;
n = N1,m = U.size(),a = a1,b = b1;
WW.resize(m);
for (int i = 0; i < m; i++) {
adj[U[i]].pb(V[i]);
adj[V[i]].pb(U[i]);
id[{U[i],V[i]}] = id[{V[i],U[i]}] = i;
}
auto x = solve(U,V);
//return ans;
#ifndef local
answer(ans.fi,ans.se);
#endif
}
#ifdef local
main() {
int n = 4;
vi U,V;
U.pb(0);
U.pb(0);
V.pb(1);
V.pb(2);
U.pb(2);
V.pb(3);
int a = 1, b = 2;
auto x = find_pair(n,U,V,a,b);
cout << x.fi <<' '<<x.se ;
}
#endif