제출 #841827

#제출 시각아이디문제언어결과실행 시간메모리
841827eltu0815Two Currencies (JOI23_currencies)C++14
0 / 100
83 ms60368 KiB
#include <bits/stdc++.h> #define MAX 100005 #define MOD 998244353 #define INF (ll)(1e18) #define inf (1987654321) using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef complex<long double> cpx; constexpr long double PI = acos(-1); int tt, n, m, k, q; int in[MAX], out[MAX], dep[MAX]; int parent[MAX][20]; int lo[MAX], hi[MAX]; int ans[MAX]; vector<pii> edge; vector<pii> chkpoint; vector<pair<pii, pll> > inp; vector<int> graph[MAX]; vector<int> event[MAX]; ll seg[MAX]; void init(int str, int ed, int node) { seg[node] = 0; if(str == ed) return; int mid = str + ed >> 1; init(str, mid, node << 1); init(mid + 1, ed, node << 1 | 1); } void update(int str, int ed, int left, int right, ll val, int node) { if(str > right || ed < left) return; if(left <= str && ed <= right) { seg[node] += val; return; } int mid = str + ed >> 1; update(str, mid, left, right, val, node << 1); update(mid + 1, ed, left, right, val, node << 1 | 1); } ll query(int str, int ed, int idx, int node) { if(str == ed) return seg[node]; int mid = str + ed >> 1; if(idx <= mid) return query(str, mid, idx, node << 1) + seg[node]; else return query(mid + 1, ed, idx, node << 1 | 1) + seg[node]; } int pv = 0; void dfs(int node, int par) { parent[node][0] = par; in[node] = ++pv; for(auto v : graph[node]) { if(v == par) continue; dep[v] = dep[node] + 1; dfs(v, node); } out[node] = pv; } int lca(int a, int b) { if(dep[a] < dep[b]) swap(a, b); int diff = dep[a] - dep[b], j = 0; while(diff) { if(diff & 1) a = parent[a][j]; diff >>= 1; ++j; } if(a == b) return a; for(int i = 19; i >= 0; --i) { if(parent[a][i] == parent[b][i]) continue; a = parent[a][i]; b = parent[b][i]; } return parent[a][0]; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m >> q; edge.resize(n - 1); for(int i = 0; i < n - 1; ++i) { int a, b; cin >> a >> b; edge[i] = {a, b}; graph[a].push_back(b); graph[b].push_back(a); } chkpoint.resize(m); for(int i = 0; i < m; ++i) cin >> chkpoint[i].second >> chkpoint[i].first; for(int i = 0; i < m; ++i) chkpoint[i].second--; sort(chkpoint.begin(), chkpoint.end()); inp.resize(q); for(int i = 0; i < q; ++i) cin >> inp[i].first.first >> inp[i].first.second >> inp[i].second.first >> inp[i].second.second; for(int i = 0; i < q; ++i) lo[i] = -1, hi[i] = m; dfs(1, 0); for(int i = 1; i <= n; ++i) for(int j = 1; j < 20; ++j) parent[i][j] = parent[parent[i][j - 1]][j - 1]; while(true) { int flag = 1; for(int i = 0; i < m; ++i) event[i].clear(); for(int i = 0; i < q; ++i) { if(lo[i] + 1 == hi[i]) continue; flag = 0; int mid = lo[i] + hi[i] >> 1; event[mid].push_back(i); } if(flag) break; init(1, n, 1); for(int i = 0; i < m; ++i) { int j = chkpoint[i].second; int u = edge[j].first, v = edge[j].second; if(dep[u] < dep[v]) swap(u, v); update(1, n, in[u], out[u], chkpoint[i].first, 1); for(auto k : event[i]) { int a = inp[k].first.first, b = inp[k].first.second; int p = lca(a, b); ll sum = query(1, n, in[a], 1); sum += query(1, n, in[b], 1); sum -= 2 * query(1, n, in[p], 1); if(sum <= inp[k].second.second) lo[k] = i; else hi[k] = i; } } } for(int i = 0; i < m; ++i) event[i].clear(); for(int i = 0; i < q; ++i) { if(lo[i] == -1) continue; event[lo[i]].push_back(i); } init(1, n, 1); for(int i = m - 1; i >= 0; --i) { for(auto k : event[i]) { int a = inp[k].first.first, b = inp[k].first.second; int p = lca(a, b); ll sum = query(1, n, in[a], 1); sum += query(1, n, in[b], 1); sum -= 2 * query(1, n, in[p], 1); if(sum <= inp[k].second.first) ans[k] = inp[k].second.first - sum; else ans[k] = -1; } int j = chkpoint[i].second; int u = edge[j].first, v = edge[j].second; if(dep[u] < dep[v]) swap(u, v); update(1, n, in[u], out[u], 1, 1); } for(int i = 0; i < q; ++i) { if(lo[i] != -1) continue; int a = inp[i].first.first, b = inp[i].first.second; int p = lca(a, b); ll sum = query(1, n, in[a], 1); sum += query(1, n, in[b], 1); sum -= 2 * query(1, n, in[p], 1); if(sum <= inp[i].second.first) ans[i] = inp[i].second.first - sum; else ans[i] = -1; } for(int i = 0; i < q; ++i) cout << ans[i] << '\n'; return 0; }

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

currencies.cpp: In function 'void init(int, int, int)':
currencies.cpp:32:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
currencies.cpp: In function 'void update(int, int, int, int, ll, int)':
currencies.cpp:43:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
currencies.cpp: In function 'll query(int, int, int, int)':
currencies.cpp:50:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
currencies.cpp: In function 'int main()':
currencies.cpp:114:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |             int mid = lo[i] + hi[i] >> 1;
      |                       ~~~~~~^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...