제출 #1262268

#제출 시각아이디문제언어결과실행 시간메모리
1262268miniobTwo Currencies (JOI23_currencies)C++20
0 / 100
26 ms5192 KiB
#include <bits/stdc++.h> using namespace std; int przod[100007][19]; int gl[100007]; int preord[100007]; int prawk[100007]; int ilemaxx[100007]; int odp[100007]; int n, m, q; vector<int> graph[100007]; vector<pair<int, int>> bramki; int t = 0; int drz[262150]; int drz2[262150]; struct zapyt{ int ind, l, r, lca, s, t, x, y; }; bool sfunkc(const zapyt& a, const zapyt& b) { return ((a.l + a.r) / 2) < ((b.l + b.r) / 2); } void dfs(int cur, int pop) { gl[cur] = gl[pop] + 1; preord[cur] = t; prawk[cur] = t; t++; if(pop != -1) { przod[cur][0] = pop; } for(auto x : graph[cur]) { if(x != pop) { dfs(x, cur); prawk[cur] = max(prawk[cur], prawk[x]); } } } int lca(int a, int b) { if(gl[a] > gl[b]) { swap(a, b); } for(int i = 18; i >= 0; i--) { if(gl[przod[b][i]] >= gl[a]) { b = przod[b][i]; } } if(a == b) { return a; } for(int i = 18; i >= 0; i--) { if(przod[a][i] != przod[b][i]) { a = przod[a][i]; b = przod[b][i]; } } return przod[a][0]; } void policzlca() { przod[1][0] = 1; for(long long i = 1; i < 19; i++) { for(long long j = 1; j <= n; j++) { przod[j][i] = przod[przod[j][i - 1]][i - 1]; } } } void dodaj(int l, int r, int curl, int curr, int gdzie, int ile) { if(l > curr || r < curl) { return; } else if(l <= curl && curr <= r) { drz[gdzie] += ile; } else { dodaj(l, r, curl, (curl + curr) / 2, 2 * gdzie, ile); dodaj(l, r, (curl + curr) / 2 + 1, curr, 2 * gdzie + 1, ile); } } int sumap(int gdzie) { gdzie += 131072; int suma = 0; while(gdzie != 0) { suma += drz[gdzie]; gdzie /= 2; } return suma; } void dodaj2(int l, int r, int curl, int curr, int gdzie, int ile) { if(l > curr || r < curl) { return; } else if(l <= curl && curr <= r) { drz2[gdzie] += ile; } else { dodaj2(l, r, curl, (curl + curr) / 2, 2 * gdzie, ile); dodaj2(l, r, (curl + curr) / 2 + 1, curr, 2 * gdzie + 1, ile); } } int sumap2(int gdzie) { gdzie += 131072; int suma = 0; while(gdzie != 0) { suma += drz2[gdzie]; gdzie /= 2; } return suma; } int main() { cin >> n >> m >> q; vector<pair<int, int>> krawww; for(int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; krawww.push_back({a, b}); graph[a].push_back(b); graph[b].push_back(a); } dfs(1, 0); policzlca(); for(int i = 0; i < m; i++) { int p, c, gdzied; cin >> p >> c; if(gl[krawww[p - 1].first] > gl[krawww[p - 1].second]) { gdzied = krawww[p - 1].first; } else { gdzied = krawww[p - 1].second; } bramki.push_back({c, gdzied}); } sort(bramki.begin(), bramki.end()); vector<zapyt> wszystkiezapyt; for(int i = 0; i < q; i++) { int s, t, x, y; cin >> s >> t >> x >> y; zapyt temp; temp.l = 0; temp.r = m; temp.ind = i; temp.lca = lca(s, t); temp.x = x; temp.y = y; temp.s = s; temp.t = t; wszystkiezapyt.push_back(temp); } for(int iter = 0; iter < 30; iter++) { sort(wszystkiezapyt.begin(), wszystkiezapyt.end(), sfunkc); int dulgp = 0; for(int i = 0; i < q; i++) { while(dulgp < (wszystkiezapyt[i].l + wszystkiezapyt[i].r) / 2) { dodaj(preord[bramki[dulgp].second], prawk[bramki[dulgp].second], 0, 131071, 1, bramki[dulgp].first); dodaj2(preord[bramki[dulgp].second], prawk[bramki[dulgp].second], 0, 131071, 1, 1); dulgp++; } if(sumap(preord[wszystkiezapyt[i].s]) + sumap(preord[wszystkiezapyt[i].t]) - 2 * sumap(preord[wszystkiezapyt[i].lca]) > wszystkiezapyt[i].y) { wszystkiezapyt[i].r = (wszystkiezapyt[i].l + wszystkiezapyt[i].r) / 2; } else { ilemaxx[wszystkiezapyt[i].ind] = sumap2(preord[wszystkiezapyt[i].s]) + sumap2(preord[wszystkiezapyt[i].t]) - 2 * sumap2(preord[wszystkiezapyt[i].lca]); wszystkiezapyt[i].l = (wszystkiezapyt[i].l + wszystkiezapyt[i].r) / 2 + 1; } } for(int i = 0; i < 262147; i++) { drz[i] = 0; drz2[i] = 0; } } for(int i = 0; i < m; i++) { dodaj(preord[bramki[i].second], prawk[bramki[i].second], 0, 131071, 1, 1); } for(int i = 0; i < q; i++) { int ilebram = sumap(preord[wszystkiezapyt[i].s]) + sumap(preord[wszystkiezapyt[i].t]) - 2 * sumap(preord[wszystkiezapyt[i].lca]); if(ilebram - ilemaxx[wszystkiezapyt[i].ind] - wszystkiezapyt[i].x <= 0) { odp[wszystkiezapyt[i].ind] = wszystkiezapyt[i].x - ilebram + ilemaxx[wszystkiezapyt[i].ind]; } else { odp[wszystkiezapyt[i].ind] = -1; } } for(int i = 0; i < q; i++) { cout << odp[i] << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...