oj.uz

Submission #301390

# Submission time Handle Problem Language Result Execution time Memory
301390 2020-09-17T21:57:04 Z Elephant52 Highway Tolls (IOI18_highway) C++11
51 / 100
 272 ms 23436 KB 
#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 search() {
  
}

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;
  depth[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);
    
    for (auto edge : adj[cur.F]) {
      if (!seen[edge.F]) {
        seen[edge.F] = 1;
        depth[edge.F] = cur.S+1;
        bfs.push(MP(edge.F, cur.S+1));	
      }
      if (depth[edge.F] > cur.S) edge_dist[cur.S].PB(edge.S);
    }
  }
  
  assert(A > 0);
  dist = ask(w)/A;
  
  int low = 1, high = tree_height;
  while (low < high) {
    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) ? low-1 : low; //depth of lower point
  
  assert(edge_dist[lower_point].size() > 0);
  low = 0, high = 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;
  }

  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]];
  
  memset(seen, 0, sizeof(seen));
  memset(depth, 0, sizeof(depth));
  for (auto& vec : edge_dist) vec.clear();
  
  bfs.push(MP(S, 1));
  seen[S] = 1;
  depth[S] = 1;
  while (!bfs.empty()) {
    pii cur = bfs.front(); bfs.pop(); //vertex, distance
    //depth[cur.F] = cur.S;
  
    for (auto edge : adj[cur.F]) {
      if (!seen[edge.F]) {
        seen[edge.F] = 1;
        depth[edge.F] = cur.S+1;
        bfs.push(MP(edge.F, cur.S+1));	
      }
      if (depth[edge.F] > cur.S) edge_dist[cur.S].PB(edge.S);
    }
  }
  
  cerr << "DEPTH: " << edge_dist[2].size() << endl;
  cerr << "DIST: " << dist << endl;
  
  low = 0, high = (int)edge_dist[dist].size()-1;
  cerr << low << ' ' << high << endl;
  
  while (low < high) {
    int mid = (low + high)/2;
    
    for (int i = 0; i <= mid; i++) w[edge_dist[dist][i]] = 1;
    ll res = ask(w);
    for (int i = 0; i <= mid; i++) w[edge_dist[dist][i]] = 0;
    
    if (res > dist*A) high = mid;	
    else low = mid+1;
  }
  cerr << "LOW: " << low << ' ' << dist << endl;
  int edge_id = edge_dist[dist][low];
  cerr << "EDGE: " << U[edge_id] << ' ' << V[edge_id] << endl;
  T = (depth[U[edge_id]] > depth[V[edge_id]]) ? U[edge_id] : V[edge_id];
  cerr << S << ' ' << T << endl;// << ' ' <<  U[candidates[low]] << ' ' << V[candidates[low]] << endl;
  cerr << "DEPTHS " << depth[47672] << ' ' << depth[55349] << endl;
  answer(S, T);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7168 KB Output is correct
2 Correct 5 ms 7168 KB Output is correct
3 Correct 5 ms 7168 KB Output is correct
4 Correct 5 ms 7168 KB Output is correct
5 Correct 5 ms 7168 KB Output is correct
6 Correct 5 ms 7168 KB Output is correct
7 Correct 5 ms 7168 KB Output is correct
8 Correct 5 ms 7168 KB Output is correct
9 Correct 5 ms 7080 KB Output is correct
10 Correct 5 ms 7168 KB Output is correct
11 Correct 5 ms 7168 KB Output is correct
12 Correct 6 ms 7076 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7168 KB Output is correct
2 Correct 20 ms 8064 KB Output is correct
3 Correct 186 ms 16264 KB Output is correct
4 Correct 179 ms 16300 KB Output is correct
5 Correct 172 ms 16228 KB Output is correct
6 Correct 174 ms 16184 KB Output is correct
7 Correct 178 ms 16360 KB Output is correct
8 Correct 184 ms 16352 KB Output is correct
9 Correct 170 ms 16472 KB Output is correct
10 Correct 178 ms 16168 KB Output is correct
11 Correct 197 ms 17172 KB Output is correct
12 Correct 204 ms 18096 KB Output is correct
13 Correct 195 ms 17300 KB Output is correct
14 Correct 190 ms 17012 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8960 KB Output is correct
2 Correct 35 ms 10736 KB Output is correct
3 Correct 65 ms 12444 KB Output is correct
4 Correct 146 ms 23396 KB Output is correct
5 Correct 150 ms 23392 KB Output is correct
6 Correct 142 ms 23384 KB Output is correct
7 Correct 140 ms 23392 KB Output is correct
8 Correct 141 ms 23388 KB Output is correct
9 Correct 136 ms 23436 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7180 KB Output is correct
2 Correct 20 ms 8320 KB Output is correct
3 Correct 129 ms 14280 KB Output is correct
4 Correct 175 ms 16148 KB Output is correct
5 Correct 171 ms 16140 KB Output is correct
6 Correct 173 ms 16168 KB Output is correct
7 Correct 167 ms 16160 KB Output is correct
8 Correct 179 ms 16036 KB Output is correct
9 Correct 174 ms 16192 KB Output is correct
10 Correct 181 ms 16176 KB Output is correct
11 Correct 188 ms 16672 KB Output is correct
12 Correct 195 ms 18112 KB Output is correct
13 Correct 184 ms 17432 KB Output is correct
14 Correct 243 ms 18052 KB Output is correct
15 Correct 222 ms 16084 KB Output is correct
16 Correct 218 ms 16308 KB Output is correct
17 Correct 236 ms 17672 KB Output is correct
18 Correct 234 ms 17352 KB Output is correct
19 Correct 192 ms 16112 KB Output is correct
20 Correct 190 ms 18680 KB Output is correct
21 Correct 191 ms 17140 KB Output is correct
22 Correct 196 ms 17148 KB Output is correct
23 Correct 209 ms 16860 KB Output is correct
24 Correct 170 ms 17544 KB Output is correct
25 Correct 205 ms 22476 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 8312 KB Output is correct
2 Correct 24 ms 8312 KB Output is correct
3 Correct 203 ms 17820 KB Output is correct
4 Correct 272 ms 18820 KB Output is correct
5 Incorrect 265 ms 20416 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 8320 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -