?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
157723527 |
Practice: mynameisminh |
342E - 19 | C++17 (GCC 7-32) | Time limit exceeded on test 18 | 5000 ms | 44720 KB | 2022-05-19 19:20:31 | 2022-05-19 19:20:31 |
#include<bits/stdc++.h> #define pb push_back #define RED 1 #define BLUE 0 #define FOR(i, l, r) for(int i = l; i <= r; i++) using namespace std; const int N = 1e5 + 5; const int lgN = 30; vector < int > adj[N]; bool visits[N], check[N]; int d[N]; int n, m, k, bit, timer; queue < int > q; vector < int > temp; int dp[N * 2][lgN], h[N]; struct ao { int ver, level; }; ao euler[2 * N]; void BFS() { FOR(i, 1, n) visits[i] = false; for(int i = 0; i < temp.size(); i++) { q.push(temp[i]); d[temp[i]] = 0; } temp.clear(); while(!q.empty()) { int u = q.front(); q.pop(); visits[u] = true; for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if(!visits[v]) { d[v] = min(d[v], d[u] + 1); q.push(v); } } } } void dfs(int u, int d) { check[u] = true; euler[timer].ver = u; euler[timer].level = d; timer++; for(auto v : adj[u]) { if(!check[v]) { dfs(v, d + 1); euler[timer].ver = u; euler[timer].level = d; timer++; } } } void prepro() { for(int i = 0; i < timer; i++) dp[i][0] = i; for(int j = 1; (1 << j) < timer; j++) { for(int i = 0; i + (1 << j) < timer; i++) { if(euler[dp[i][j - 1]].level <= euler[dp[i + (1 << j - 1)][j - 1]].level) dp[i][j] = dp[i][j - 1]; else dp[i][j] = dp[i + (1 << j - 1)][j - 1]; } } } int get_dist(int a, int b) { if(a == b) return 0; //cout << a << " " << b << endl; a = h[a] - 1, b = h[b] - 1; if(a > b) swap(a, b); int p = 31 - __builtin_clz(b - a); int c = dp[a][p], d = dp[b - (1 << p)][p]; int res = min(euler[dp[a][p]].level, euler[dp[b - (1 << p)][p]].level); //cout << euler[a].level << " " << euler[b].level << " " << res << endl; return euler[a].level + euler[b].level - 2 * res; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 1; i <= n; i++) d[i] = INT_MAX; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } memset(check, false, sizeof(check)); memset(h, -1, sizeof(h)); k = sqrt(m); timer = 0; dfs(1, 0); prepro(); for(int i = 0; i < timer; i++) { //cout << euler[i].ver << " "; if(h[euler[i].ver] == -1) h[euler[i].ver] = i + 1; } q.push(1); d[1] = 0; for(int i = 0; i < m; i++) { if(i % k == 0) BFS(); int t, x; cin >> t >> x; if(t == 1) { temp.push_back(x); d[x] = 0; } else { int res = d[x]; for(int l = 0; l < temp.size(); l++) { //cout << temp[l] << " "; res = min(res, get_dist(x, temp[l])); } cout << res << endl; } } }
?
?
?
?