Submission #1137890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137890		fryingduc	Stations (IOI20_stations)	C++20	100 / 100	304 ms	592 KiB

stations

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#include "stations.h"
#endif

const int maxn = 1005;
vector<int> g[maxn];
int n, k, q;
int tin[maxn], tout[maxn];
int lb[maxn];
int timer;

void pre_dfs(int u, int prev, int depth) {
  if(depth % 2 == 0) lb[u] = timer++;
  for(auto v:g[u]) {
    if(v == prev) continue;
    pre_dfs(v, u, depth + 1);
  }
  if(depth & 1) lb[u] = timer++;
}

vector<int> label(int n, int k, vector<int> adj_u, vector<int> adj_v) {
  for(int i = 0; i < n; ++i) {
    g[i].clear();
  }
  for(int i = 0; i < (int)adj_u.size(); ++i) {
    g[adj_u[i]].push_back(adj_v[i]);
    g[adj_v[i]].push_back(adj_u[i]);
  }
  timer = 0;
  pre_dfs(0, -1, 0);
  
  vector<int> hehe;
  for(int i = 0; i < n; ++i) {
    hehe.push_back(lb[i]);
  }
  
  return hehe;
}

int find_next_station(int s, int t, vector<int> adj) {
//  debug(s, t, adj);
  if(s > adj[0]) {
    if(s < t || t < adj[0]) return adj[0];
    int nxt = 0;
    for(int i = 0; i < (int)adj.size(); ++i) {
      if(adj[i] <= t) {
        nxt = max(nxt, adj[i]);
      }
    }
    return nxt;
  }
  if(s > t || t > adj.back()) return adj.back();
  int nxt = 1e9;
  for(int i = 0; i < (int)adj.size(); ++i) {
    if(adj[i] >= t) {
      nxt = min(nxt, adj[i]);
    }
  }
  return nxt;
}

#ifdef duc_debug
int par[maxn];
void dfs(int u, int prev) {
  for(auto v:g[u]) {
    if(v == prev) continue;
    par[v] = u;
    dfs(v, u);
  }
}

int get_next(int u, int v) {
  par[v] = -1;
  dfs(v, -1);
  
  return par[u];
}

void solve() {
  cin >> n >> k;
  vector<int> au, av;
  for(int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    au.push_back(u);
    av.push_back(v);
  }
  
  vector<int> lab = label(n, k, au, av);
  
  cin >> q;
  while(q--) {
    int u, v; cin >> u >> v;
    vector<int> dark;
    for(auto i:g[u]) {
      dark.push_back(lab[i]);
    }
    
    sort(dark.begin(), dark.end());
    
    int x = find_next_station(lab[u], lab[v], dark);
//    debug(x, get_next(u, v));
    if(x != lab[get_next(u, v)]) {
      assert(0);
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  int t; cin >> t;
  while(t--) {
    solve();
  }

  return 0;
}
#endif

/*
1
5 10
0 1 
1 2
1 3
2 4
2
2 0
3 1

1
6 5
0 1
1 2
1 3
0 4
4 5
3
4 0
5 0
4 2
*/

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 16 / 16
• Subtask 4: 10 / 10
• Subtask 5: 61 / 61