제출 #1237674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237674		mychecksedad	통행료 (IOI18_highway)	C++20	6 / 100	56 ms	29576 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define ll long long int
#define pii pair<int,int>
const int N = 2e5+100;

int s[N], dep[N], PAR[N];
vector<pii> g[N];
vi D[N];
vi D2[N];
bitset<N> VIS;
vi C[N];
vector<vi> QC[N];
void pre(int v, int p){
  s[v] = 1;
  for(auto [u, id]: g[v]){
    if(!VIS[u] && u != p){
      pre(u, v);
      s[v] += s[u];
    }
  }
}
int num;
int centro(int v, int p){
  for(auto [u, id]: g[v]){
    if(!VIS[u] && u != p){
      if(s[u] >= (num+1)/2) return centro(u, v);
    }
  }
  return v;
}
void f(int v, int dep){
  pre(v, v);
  num = s[v];
  v = centro(v, v);
  C[dep].pb(v);
  vi q;
  for(auto [u, id]: g[v]){
    if(!VIS[u]){
      q.pb(id);
    }
  }
  QC[dep].pb(q);
  VIS[v] = 1;
  for(auto [u, id]: g[v]){
    if(!VIS[u]) f(u, dep + 1);
  }
}
void dfs(int v, int p){
  s[v] = 1;
  D[dep[v]].pb(v);
  for(auto [u, id]: g[v]){
    if(!VIS[u] && u != p){
      PAR[u] = id;
      dep[u] = dep[v] + 1;
      dfs(u, v);
      s[v] += s[u];
    }
  }
}
void dfs2(int v, int p){
  s[v] = 1;
  D2[dep[v]].pb(v);
  for(auto [u, id]: g[v]){
    if(!VIS[u] && u != p){
      PAR[u] = id;
      dep[u] = dep[v] + 1;
      dfs2(u, v);
      s[v] += s[u];
    }
  }
}
void gg(int v, int node, int idd){
  pre(v, v);
  num = s[v];
  v = centro(v, v);
  if(v == node){
    for(auto [u, id]: g[v]){
      if(id == idd){
        PAR[u] = id;
        dep[u] = 1;
        dfs(u, v);
        break;
      }
    }
  }

  VIS[v] = 1;
  for(auto [u, id]: g[v]){
    if(!VIS[u]) gg(u, node, idd);
  }
}
void ggg(int v, int node, int idd, int idd2){
  pre(v, v);
  num = s[v];
  v = centro(v, v);
  if(v == node){
    for(auto [u, id]: g[v]){
      if(id == idd){
        // cerr << u << ' ';
        PAR[u] = id;
        dep[u] = 1;
        dfs(u, v);
      }
      if(id == idd2){
        // cerr << u << ' ';
        PAR[u] = id;
        dep[u] = 1;
        dfs2(u, v);
      }
    }
  }

  VIS[v] = 1;
  for(auto [u, id]: g[v]){
    if(!VIS[u]) ggg(u, node, idd, idd2);
  }
}




void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
  int m = U.size();

  for(int i = 0; i < m; ++i){
    g[U[i]].pb({V[i], i});
    g[V[i]].pb({U[i], i});
  }

  vi w(m);
  ll val = ask(w);
  int k = val / A;

  int l = 0, r = m - 2, res = m-1;
  while(l <= r){
    int mid = l+r>>1;
    w.clear();
    w.resize(m);
    for(int j = 0; j <= mid; ++j) w[j] = 1;
    ll y = ask(w);
    if(y != val){
      res = mid;
      r = mid - 1;
    }else{
      l = mid + 1;
    }
  }

  int x = U[res];
  int y = V[res];

  queue<pii> q;
  q.push({x, 0});
  q.push({y, 1});
  vector<pii> dist(n, {-1, -1});
  vi par(n);
  dist[x] = {0, 0};
  dist[y] = {0, 1};
  par[x] = par[y] = res;
  while(!q.empty()){
    int v = q.front().ff; int tp = q.front().ss; q.pop();
    for(auto [u, id]: g[v]){
      if(dist[u].ff == -1){
        dist[u].ff = dist[v].ff + 1;
        dist[u].ss = dist[v].ss;
        par[u] = id;
        q.push({u, dist[u].ss});
      }
    }
  }
  par[x] = -1;
  l = 0, r = n - 1, res = n - 1;
  while(l <= r){
    int mid = l+r>>1;
    w.clear();
    w.resize(m, 1);

    for(int j = 0; j <= mid; ++j) if(par[j] != -1) w[par[j]] = 0;
    ll y = ask(w);
    if(y != val){
      l = mid + 1;
    }else{
      r = mid - 1;
      res = mid;
    }
  }
  int t = res;
  par[x] = par[y];
  par[y] = -1;


  l = 0, r = n - 1;
  while(l <= r){
    int mid = l+r>>1;
    w.clear();
    w.resize(m, 1);

    for(int j = mid; j < n; ++j) if(par[j] != -1) w[par[j]] = 0;
    ll y = ask(w);
    if(y != val){
      r = mid - 1;
    }else{
      l = mid + 1;
      res = mid;
    }
  }
  int s = res;
  // cerr << s << ' ' << t << '\n';
  answer(s, t);
}

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