Submission #301286

#	Time	Username	Problem	Language	Result	Execution time	Memory
301286		Elephant52	통행료 (IOI18_highway)	C++11	18 / 100	266 ms	23436 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int>> vpi;

#define INF 1000000000
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i,a,b) for (int i = a; i < b; i++)

typedef struct node {
  int vertex, edge, dist;
  node() {};
  node(int a, int b, int c) : vertex(a), edge(b), dist(c) {};
} node;

vpi adj[90000];
vi tree_adj[90000];
vi edge_dist[90000];
bool seen[90000];
int subtree_sizes[90000];
int depth[90000];

void make_spanning_tree(int cur) {
  seen[cur] = 1;
  for (auto p : adj[cur]) {
    int edge = p.F;
    if (!seen[edge]) {
      make_spanning_tree(edge);
      tree_adj[cur].PB(edge);
      tree_adj[edge].PB(cur);
    }
  }
}

void find_sizes(int cur) {
  seen[cur] = 1;
  subtree_sizes[cur] = 1;
  for (auto edge : tree_adj[cur]) {
    if (!seen[edge]) {
      find_sizes(edge);
      subtree_sizes[cur] += subtree_sizes[edge];
    }
  }
}

int find_centroid(int N) {
  find_sizes(0);
  int centroid = 0, largest_subtree, nxt = 0;
  do {
    centroid = nxt;
    largest_subtree = 0;
    for (auto edge : adj[centroid]) {
      if (subtree_sizes[edge.F] > largest_subtree) {
        largest_subtree = subtree_sizes[N];
        nxt = edge.F;
      }	
    }
  } while(largest_subtree >= N/2+5 && N - subtree_sizes[centroid] >= N/2+5);
  return centroid;
}

void find_pair(int N, vi U, vi V, int A, int B) {
  int S = 0, T = 0, M = V.size();
  ll dist;
  
  vi w(M, 0); //query edge list
  
  rep(i,0,M) {
    adj[U[i]].emplace_back(V[i], i);
    adj[V[i]].emplace_back(U[i], i);
  }
  
  make_spanning_tree(0);
  memset(seen, 0, sizeof(seen));
  
  queue<pii> bfs;
  int root = find_centroid(N);
  cerr << "root " << root << endl;
  bfs.push(MP(root, 1));
  
  int tree_height = 0;
  int counter = 0;
  memset(seen, 0, sizeof(seen));
  seen[root] = 1;
  while (!bfs.empty()) {
    pii cur = bfs.front(); bfs.pop(); //vertex, distance
    depth[cur.F] = cur.S;
    tree_height = max(tree_height, cur.S);
    //if (counter++ < 10) cerr << "WORKING?" << endl;
    
    for (auto edge : adj[cur.F]) {
      edge_dist[cur.S].PB(edge.S);
      if (!seen[edge.F]) {
        seen[edge.F] = 1;
        bfs.push(MP(edge.F, cur.S+1));	
      }
    }
  }
  
  assert(A > 0);
  dist = ask(w)/A;
  
  int low = 1, high = tree_height;
  while (low < high) {
    //cerr << "WORKS: " << low << ' ' << high << endl;
    int mid = (low + high)/2;
    
    for (int i = tree_height-1; i >= mid; i--) for (auto edge : edge_dist[i]) w[edge] = 1;
    ll res = ask(w);
    for (int i = tree_height-1; i >= mid; i--) for (auto edge : edge_dist[i]) w[edge] = 0;
    
    if (res > dist*A) low = mid+1;	
    else high = mid;
    

  }
  
  int lower_point = low-1; //depth of lower point
  if (lower_point == 0) lower_point++;
  
  assert(edge_dist[lower_point].size() > 0);
  low = 0, high = (int)edge_dist[lower_point].size()-1;
  
  while (low < high) {
    int mid = (low + high)/2;
    
    for (int i = 0; i <= mid; i++) w[edge_dist[lower_point][i]] = 1;
    ll res = ask(w);
    for (int i = 0; i <= mid; i++) w[edge_dist[lower_point][i]] = 0;
    
    if (res > dist*A) high = mid;	
    else low = mid+1;
    
    
  }
   cerr << "HI" << endl;
  //return;
  //S = min(U[edge_dist[lower_point][low]], V[edge_dist[lower_point][low]]);
  cerr << low << ' ' << edge_dist[lower_point].size() << ' ';
  cerr << S << ' ' << edge_dist[lower_point][low] << endl;
  assert(edge_dist[lower_point][low] < N);
  if (depth[U[edge_dist[lower_point][low]]] > depth[V[edge_dist[lower_point][low]]]) S = U[edge_dist[lower_point][low]];
  else S = V[edge_dist[lower_point][low]];
  
  cerr << "S " << U[edge_dist[lower_point][low]] << ' ' << V[edge_dist[lower_point][low]] << endl;
  cerr << "depth: " << depth[U[edge_dist[lower_point][low]]] << ' ' <<  depth[V[edge_dist[lower_point][low]]] << endl;

  queue<node> bfs2;
  bfs2.push(node(S, 0, 0));
  assert(S < N);
  seen[S] = 1;
  memset(seen, 0, sizeof(seen));
  memset(depth, 0, sizeof(depth));
  vi candidates;
  while (!bfs2.empty()) {
    auto cur = bfs2.front(); bfs2.pop();
    depth[cur.vertex] = cur.dist;
    if (dist == cur.dist) {
//      assert(cur.edge < M);
      candidates.PB(cur.edge);
//      w[cur.edge] = 1;
//      ll res = ask(w);
//      if (res > dist*A) {
//        T = cur.vertex;
//        break;
//      }
//      w[cur.edge] = 0;
    }
    
    for (auto edge : adj[cur.vertex]) {
      assert(edge.F < N);
      if (!seen[edge.F]) {
        seen[edge.F] = 1;
        bfs2.push(node(edge.F, edge.S, cur.dist+1));
      }
    }
  }
  
  cerr << S << ' ' << T << endl;
  
  low = 0, high = candidates.size()-1;
  //for (auto a : w) cout << a << ' '; cout << endl;
  while (low < high) {
    int mid = (low + high)/2;
    
    for (int i = 0; i <= mid; i++) w[candidates[i]] = 1;
    ll res = ask(w);
    for (int i = 0; i <= mid; i++) w[candidates[i]] = 0;
    
    if (res > dist*A) high = mid;	
    else low = mid+1;
    
    
  }
  //for (auto a : w) cout << a << ' '; cout << endl;
  //for (auto p : candidates) cerr << "CANDIDATE: " << U[p] << ' ' << V[p] << endl;
  T = (depth[U[candidates[low]]] >= depth[V[candidates[low]]] ) ? U[candidates[low]] : V[candidates[low]];
  
  cerr << S << ' ' << T << ' ' <<  U[candidates[low]] << ' ' << V[candidates[low]] << endl;
  
  answer(S, T);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:90:7: warning: unused variable 'counter' [-Wunused-variable]
   90 |   int counter = 0;
      |       ^~~~~~~

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