Submission #1114325

#TimeUsernameProblemLanguageResultExecution timeMemory
1114325ooscodeTwo Currencies (JOI23_currencies)C++17
100 / 100
1744 ms71040 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ld long double #define F first #define S second #define pb push_back #define all(x) x.begin() , x.end() #define debug while(1) cout << "Test\n" const int N = 1e5 + 10; const int mod = 1e9 + 7; const int INF = 1e18 + 10; int n , m , q; int seg[N << 2]; int f[N]; int l[N]; int r[N]; int mid[N]; vector<int> g[N]; vector<pair<int , int>> e; vector<pair<int , int>> vec; int x[N]; int y[N]; int s[N]; int en[N]; int par[N][20]; int lc[N]; vector<int> qu[N]; int st[N]; int fn[N]; int h[N]; int tim; void dfs(int v) { st[v] = ++tim; for(int i = 1 ; i < 20 ; i++) par[v][i] = par[par[v][i-1]][i-1]; for(auto u : g[v]) if(u != par[v][0]) { par[u][0] = v; h[u] = h[v] + 1; dfs(u); } fn[v] = tim; } int lca(int v , int u) { if(h[v] < h[u]) swap(v , u); int he = h[v] - h[u]; for(int i = 0 ; i < 20 ; i++) if((1ll << i) & he) v = par[v][i]; if(v == u) return v; for(int i = 19 ; ~i ; i--) if(par[v][i] != par[u][i]) v = par[v][i] , u = par[u][i]; return par[v][0]; } void upd(int v , int tl , int tr , int l , int r , int x) { // cout << v << " " << tl << " " << tr << " " << l << " " << r << " " << x << "\n"; if(l > r) return; if(tl == l && tr == r) { seg[v] += x; return; } int tm = (tl + tr) >> 1; int cl = v << 1 , cr = cl | 1; upd(cl , tl , tm , l , min(tm , r) , x); upd(cr , tm + 1 , tr , max(tm+1 , l) , r , x); } int ask(int v , int tl , int tr , int p) { if(tl == tr) return seg[v]; int tm = (tl + tr) >> 1; int cl = v << 1 , cr = cl | 1; if(tm >= p) return ask(cl , tl , tm , p) + seg[v]; return ask(cr , tm+1 , tr , p) + seg[v]; } void solve() { cin >> n >> m >> q; for(int i = 1 ; i < n ; i++) { int v , u; cin >> v >> u; e.pb({v , u}); g[v].pb(u); g[u].pb(v); } dfs(1); for(int i = 1 ; i <= m ; i++) { int id , x; cin >> id >> x; vec.pb({x , id}); } sort(all(vec)); for(int i = 1 ; i <= q ; i++) { cin >> s[i] >> en[i] >> x[i] >> y[i]; lc[i] = lca(s[i] , en[i]); l[i] = 0; r[i] = m+1; mid[i] = (l[i] + r[i]) >> 1; qu[mid[i]].pb(i); } for(int i = 1 ; i <= m ; i++) { // cout << "kir " << i << "\n"; int v = e[vec[i-1].S-1].F; int u = e[vec[i-1].S-1].S; if(v == par[u][0]) swap(v , u); upd(1 , 1 , n , st[v] , fn[v] , 1); } for(int i = 1 ; i <= q ; i++) f[i] = ask(1 , 1 , n , st[s[i]]) + ask(1 , 1 , n , st[en[i]]) - 2 * ask(1 , 1 , n , st[lc[i]]); // , cout << i << " " << f[i] << "\n"; for(int t = 1 ; t <= 20 ; t++) { for(int i = 1 ; i <= 4 * n ; i++) seg[i] = 0; for(int i = 1 ; i <= m ; i++) { int v = e[vec[i-1].S-1].F; int u = e[vec[i-1].S-1].S; if(v == par[u][0]) swap(v , u); upd(1 , 1 , n , st[v] , fn[v] , vec[i-1].F); for(auto id : qu[i]) { // if(id == 1) cout << l[id] << " " << r[id] << " " << mid[id] << " oo " << ask(1 , 1 , n , st[s[id]]) + ask(1 , 1 , n , st[en[id]]) - 2 * ask(1 , 1 , n , st[lc[id]]) << "\n"; if(ask(1 , 1 , n , st[s[id]]) + ask(1 , 1 , n , st[en[id]]) - 2 * ask(1 , 1 , n , st[lc[id]]) <= y[id]) l[id] = mid[id]; else r[id] = mid[id]; mid[id] = (l[id] + r[id]) >> 1; } } for(int i = 1 ; i <= m ; i++) qu[i].clear(); for(int i = 1 ; i <= q ; i++) qu[mid[i]].pb(i); } // for(int i = 1 ; i <= q ; i++) // cout << l[i] << " " << r[i] << " " << mid[i] << "\n"; // cout << "khob kir\n"; for(int i = 1 ; i <= 4 * n ; i++) seg[i] = 0; for(int i = 1 ; i <= m ; i++) { int v = e[vec[i-1].S-1].F; int u = e[vec[i-1].S-1].S; if(v == par[u][0]) swap(v , u); upd(1 , 1 , n , st[v] , fn[v] , 1); for(auto id : qu[i]) f[id] -= ask(1 , 1 , n , st[s[id]]) + ask(1 , 1 , n , st[en[id]]) - 2 * ask(1 , 1 , n , st[lc[id]]); } for(int i = 1 ; i <= q ; i++) cout << max(-1ll , x[i] - f[i]) << "\n"; // cout << "GA\n"; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n = 1; // cin >> n; while(n--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...