제출 #1237211

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

highway

#include "highway.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 90001, inf = 2e9;

vector<pii> edges[LIM];
vi tin(LIM),tout(LIM);
int up[LIM][17];
int timer = 0;
vi edgs,edgs2;
void dfs(int node,int p) {
  tin[node] = timer++;
  up[node][0] = p;
  for (int i=1;i<17;i++) {
    up[node][i] = up[up[node][i-1]][i-1];
  }
  for (auto it : edges[node]) {
    if (it.ff == p) continue;
    edgs2.push_back(it.ss);
    dfs(it.ff,node);
    edgs.push_back(it.ss);
  }
  tout[node] = timer-1;
}

bool anc(int a,int b) {
  return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a,int b) { 
  if (anc(a,b)) return a;
  if (anc(b,a)) return b;
  for (int i = 16;i>=0;i--) {
    if (!anc(up[a][i],b)) a = up[a][i];
  }
  return up[a][0];
}
int maxtout(int a,int b) {
  if (tout[a] <= tout[b]) return a;
  return b;
}
int maxlow(int a,int b) {
  if (tin[a] >= tin[b]) return a;
  return b;
}
void find_pair(signed N, std::vector<signed> U, std::vector<signed> V, signed A, signed B) {
  int M = U.size();
  vector<pii> edg;
  for (int i = 0;i<M;i++) {
    edges[U[i]].push_back({V[i],i});
    edges[V[i]].push_back({U[i],i});
    edg.push_back({U[i],V[i]});
  }
  dfs(0,0);/* 
  for (auto it : edgs) cout << it << ' ';
  cout << '\n';
  for (auto it : edgs2) cout << it << ' ';
  cout << '\n'; */
  int l = 1;
  int r = M;
  int init = ask(vector<int32_t>(M,0));
  int L,R;
  while (l<=r) {
    vector<int32_t> q(M,0);
    int m = (l+r) >> 1;
    for (int j = 0;j<m;j++) q[edgs[j]] = 1;
    int toll = ask(q);
    int pass = (toll-init)/(B-A);
    if (pass) r = m-1;
    else l = m+1;
  }
  L = l;
  l = 1;
  r = M;
  while (l<=r) {
    vector<int32_t> q(M,0);
    int m = (l+r) >> 1;
    for (int j = M-1;j >= m-1;j--) q[edgs2[j]] = 1;
    int toll = ask(q);
    int pass = (toll-init)/(B-A);
    if (pass) l = m+1;
    else r = m-1;
  }
  R = r;
  int alt1 = maxlow(edg[edgs[L-1]].ff,edg[edgs[L-1]].ss);
  int alt2 = maxtout(edg[edgs2[R-1]].ff,edg[edgs2[R-1]].ss);
  answer(alt1,alt2);
}

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