제출 #1118608

#제출 시각아이디문제언어결과실행 시간메모리
1118608BulaTraffickers (RMI18_traffickers)C++14
75 / 100
3566 ms65576 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int mod = 1e9 + 7, N = 3e4 + 5, LOG = 20; vector<int> adj[N]; int s[N], e[N], depth[N], par[N]; int timer = 0; void dfs(int v, int p){ s[v] = ++timer; par[v] = p; for(auto x : adj[v]){ if(x == p) continue; depth[x] = depth[v] + 1; dfs(x, v); } e[v] = timer; } int et[2 * N], lg[2 * N], tin[N]; pair<int, int> st[LOG + 1][2 * N]; void dfs1(int v, int p) { et[++timer] = v; tin[v] = timer; for(int u : adj[v]){ if (u == p) continue; dfs1(u, v); et[++timer] = v; } } pair<int, int> rmq(int l, int r){ int i = lg[r - l + 1]; return min(st[i][l], st[i][r - (1 << i) + 1]); } int lca(int u, int v){ if(tin[u] > tin[v]) swap(u, v); return rmq(tin[u], tin[v]).second; } int fenwick[N][LOG + 1][LOG + 1] = {}; int sum(int r, int i, int k) { int res = 0; while (r >= 0) { res += fenwick[r][i][k]; r = (r & (r + 1)) - 1; } return res; } int get(int l, int r, int i, int k) { return sum(r, i, k) - sum(l - 1, i, k); } void inc(int j, int delta, int i, int k) { while (j < N) { fenwick[j][i][k] += delta; j |= j + 1; } } int Get(int u, int v, int i, int k){ int x = lca(u, v); return get(1LL, s[u], i, k) + get(1LL, s[v], i, k) - get(1LL, s[x], i, k) - get(1LL, s[par[x]], i, k); } void upd(int v, int x, int i, int k){ inc(s[v], x, i, k); inc(e[v] + 1, -x, i, k); } vector<int> path(int u, int v){ int x = lca(u, v), a = u, b = v; vector<int> p; while(a != x){ p.push_back(a); a = par[a]; } p.push_back(x); vector<int> q; while(b != x){ q.push_back(b); b = par[b]; } reverse(q.begin(), q.end()); for(auto k : q) p.push_back(k); return p; } void add(int u, int v){ vector<int> p = path(u, v); int k = p.size(); for(int i = 0; i < k; i++){ upd(p[i], 1, i, k); } } void del(int u, int v){ vector<int> p = path(u, v); int k = p.size(); for(int i = 0; i < k; i++){ upd(p[i], -1, i, k); } } ll calc(int i, int k, int t1, int t2){ t1--; ll val1 = max(0, (t2 + k - i) / k); ll val2 = max(0, (t1 + k - i) / k); val1 -= val2; return val1; } void query(int u, int v, int t1, int t2){ vector<int> p = path(u, v); ll ans = 0; for(int i = 0; i <= LOG; i++){ for(int k = 1; k <= LOG; k++){ ans += 1LL * calc(i, k, t1, t2) * Get(u, v, i, k); } } cout << ans << '\n'; } main(){ int tt = 1; //cin >> tt; while(tt--){ int n; cin >> n; for(int i = 1; i <= n - 1; i++){ int x, y; cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); } dfs(1, 0); timer = 0; dfs1(1, 0); for(int i = 1; i <= 2 * n; i++) st[0][i] = {depth[et[i]], et[i]}; for(int i = 1; i <= LOG; i++){ for(int j = 1; j + (1 << i) - 1 <= 2 * n; j++){ st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]); } } lg[1] = 0; for(int i = 2; i <= 2 * n; i++) lg[i] = lg[i / 2] + 1; int k; cin >> k; for(int i = 0; i < k; i++){ int x, y; cin >> x >> y; add(x, y); } int q; cin >> q; while(q--){ int t; cin >> t; if(t == 1){ int x, y; cin >> x >> y; add(x, y); }else if(t == 2){ int x, y; cin >> x >> y; del(x, y); }else{ int x, y, t1, t2; cin >> x >> y >> t1 >> t2; query(x, y, t1, t2); } } } }

컴파일 시 표준 에러 (stderr) 메시지

traffickers.cpp:112:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  112 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...