제출 #1210399

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210399		loiiii12358	통행료 (IOI18_highway)	C++20	0 / 100	1587 ms	327680 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<pair<bool,pair<int,int>>> edges;
vector<vector<int>> to;
vector<int32_t> vec;
int len,n,a,b,s,e;

vector<int> subtrees(int u){
  vector<int> subtree(n,1);
  stack<pair<int,int>> dfs,trace;
  dfs.push({u,-1});
  int par,now,v;
  while(!dfs.empty()){
    now=dfs.top().first;
    par=dfs.top().second;
    dfs.pop();
    for(int i=0;i<to[now].size();i++){
      if(edges[to[now][i]].first==false){
        continue;
      }else if(edges[to[now][i]].second.first==now){
        v=edges[to[now][i]].second.second;
      }else{
        v=edges[to[now][i]].second.first;
      }
      if(v!=par){
        dfs.push({v,now});
      }
    }
    if(par!=-1){
      trace.push({par,now});
      // subtree[par]+=subtree[now];
    }
  }
  while(!trace.empty()){
    par=trace.top().first;
    now=trace.top().second;
    trace.pop();
    subtree[par]+=subtree[now];
  }
  return subtree;
}

int centroid(int u){
  int par,now,v;
  vector<int> subtree=subtrees(u);
  now=u;
  while(true){
    par=now;
    for(int i=0;i<to[now].size();i++){
      if(edges[to[now][i]].first==false){
        continue;
      }else if(edges[to[now][i]].second.first==now){
        v=edges[to[now][i]].second.second;
      }else{
        v=edges[to[now][i]].second.first;
      }
      if(subtree[v]*2>=subtree[u]){
        now=v;
      }
    }
    if(now==par){
      break;
    }
  }
  return now;
}

int solve(int u,int dep){
  // cout << u << ' ' << dep << '\n';
  // for(int i=0;i<edges.size();i++){
  //   cout << edges[i].first << " \n"[i+1==edges.size()];
  // }
  int now,par,d,v,l,r;
  vector<pair<int,int>> pos;
  stack<pair<pair<int,int>,int>> dfs;
  dfs.push({{u,-1},0});
  while(!dfs.empty()){
    now=dfs.top().first.first;
    par=dfs.top().first.second;
    d=dfs.top().second;
    dfs.pop();
    // cout << now << ' ' << par << ' ' << d << '\n';
    for(int i=0;i<to[now].size();i++){
      // cout << to[now][i] << ' ' << edges[to[now][i]].first << '\n';
      if(edges[to[now][i]].first==false){
        continue;
      }else if(edges[to[now][i]].second.first==now){
        v=edges[to[now][i]].second.second;
      }else{
        v=edges[to[now][i]].second.first;
      }
      if(v==par){
        continue;
      }
      if(d==dep-1){
        pos.push_back({v,to[now][i]});
      }else{
        dfs.push({{v,now},d+1});
      }
    }
  }
  // cout << pos.size() << '\n';
  l=0;r=pos.size()-1;
  while(l!=r){
    int m=(l+r)/2;
    fill(vec.begin(),vec.end(),0);
    for(int i=0;i<=m;i++){
      vec[pos[i].second]=1;
    }
    if(ask(vec)!=len*a){
      r=m;
    }else{
      l=m+1;
    }
  }
  // cout << pos[l].first << '\n';
  return pos[l].first;
}

void divide(int u){
  int cen=centroid(u),tmp=0,v,cnt,now,par;
  // cout << u << ' ' << cen << '\n';
  vector<int> subtree=subtrees(cen),use,unuse;
  vector<pair<int,int>> order;
  for(int i=0;i<to[cen].size();i++){
    if(edges[to[cen][i]].first==false){
      continue;
    }else if(edges[to[cen][i]].second.first==cen){
      v=edges[to[cen][i]].second.second;
    }else{
      v=edges[to[cen][i]].second.first;
    }
    order.push_back({subtree[v],to[cen][i]});
  }
  // for(int i=0;i<subtree.size();i++){
  //   cout << subtree[i] << " \n"[i+1==subtree.size()];
  // }
  sort(order.begin(),order.end());
  fill(vec.begin(),vec.end(),0);
  for(int i=order.size()-1;i>=0;i--){
    if((tmp+order[i].first)*2<subtree[cen]){
      tmp+=order[i].first;
      use.push_back(order[i].second);
    }else{
      unuse.push_back(order[i].second);
      edges[unuse.back()].first=false;
    }
  }
  stack<pair<int,int>> dfs;
  dfs.push({cen,-1});
  while(!dfs.empty()){
    now=dfs.top().first;
    par=dfs.top().second;
    dfs.pop();
    for(int i=0;i<to[now].size();i++){
      if(edges[to[now][i]].first==false){
        continue;
      }else if(edges[to[now][i]].second.first==now){
        v=edges[to[now][i]].second.second;
      }else{
        v=edges[to[now][i]].second.first;
      }
      vec[to[now][i]]=1;
      if(v!=par){
        dfs.push({v,now});
      }
    }
  }
  // for(int i=0;i<vec.size();i++){
  //   cout << vec[i] << " \n"[i+1==vec.size()];
  // }
  tmp=ask(vec);
  cnt=(tmp-len*a)/(b-a);
  // cout << cnt << ' ' << len << '\n';
  if(cnt==len){
    divide(cen);
  }else if(cnt==0){
    for(int i=0;i<use.size();i++){
      edges[use[i]].first=false;
    }
    for(int i=0;i<unuse.size();i++){
      edges[unuse[i]].first=true;
    }
    divide(cen);
  }else{
    s=solve(cen,cnt);
    for(int i=0;i<use.size();i++){
      edges[use[i]].first=false;
    }
    for(int i=0;i<unuse.size();i++){
      edges[unuse[i]].first=true;
    }
    e=solve(cen,len-cnt);
  }
}

void find_pair(int32_t N, std::vector<int32_t> U, std::vector<int32_t> V, int32_t A, int32_t B) {
  edges.resize(U.size());
  to.resize(N);
  for(int i=0;i<U.size();i++){
    to[U[i]].push_back(i);
    to[V[i]].push_back(i);
    edges[i]={true,{U[i],V[i]}};
  }
  vec.resize(U.size(),0);
  len=ask(vec)/A;
  n=N;a=A;b=B;
  divide(0);
  answer(s,e);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31