제출 #893781

#제출 시각아이디문제언어결과실행 시간메모리
893781lolismekTourism (JOI23_tourism)C++14
100 / 100
1232 ms25060 KiB
#include <algorithm> #include <iostream> #include <fstream> #include <climits> #include <vector> #include <deque> #include <queue> #include <stack> #include <map> #include <set> #include <random> #include <chrono> // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") using ull = unsigned long long; using ll = long long; //#define int __int128 //#define int ll #define pii pair <int, int> #define all(a) (a).begin(), (a).end() #define fr first #define sc second #define pb push_back #define lb lower_bound #define ub upper_bound #define vt vector #define FOR(a, b) for(int i = (a); ((a) <= (b) ? i <= (b) : i >= (b));((a) <= (b) ? i++ : i--)) #define sz(x) (int)(x).size() // ? #define YES fout << "YES\n" #define NO fout << "NO\n" using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rangerng(int l, int r){ return uniform_int_distribution<>(l, r)(rng); } //////////////////////////////////////////////////////////////////////////////////// // ifstream fin("input.in"); // ofstream fout("output.out"); #define fin cin #define fout cout const int NMAX = 1e5 + 5; // ? vt <int> adj[NMAX + 1]; int c[NMAX + 1]; vt <pii> quer[NMAX + 1]; int Ans[NMAX + 1]; int sz[NMAX + 1]; int par[NMAX + 1]; int hvChild[NMAX + 1]; int lvl[NMAX + 1]; void expl(int node, int parent){ par[node] = parent; sz[node] = 1; lvl[node] = lvl[parent] + 1; int maxi = 0; for(int child : adj[node]){ if(child != parent){ expl(child, node); sz[node] += sz[child]; if(sz[child] > maxi){ maxi = sz[child]; hvChild[node] = child; } } } } int Id = 0; int id[NMAX + 1]; int head[NMAX + 1]; int last[NMAX + 1]; int Time = 0; int pos[NMAX + 1]; void hvFirst(int node, int parent){ pos[node] = ++Time; if(hvChild[parent] != node){ id[node] = ++Id; head[Id] = node; }else{ id[node] = id[parent]; } last[id[node]] = node; if(hvChild[node] != 0){ hvFirst(hvChild[node], node); } for(int child : adj[node]){ if(child != parent && child != hvChild[node]){ hvFirst(child, node); } } } namespace AIB{ int n; int aib[NMAX + 2]; void init(int _n){ n = _n + 1; FOR(1, n){ aib[i] = 0; } } int lsb(int x){ return x & -x; } void update(int pos, int val){ pos++; for(int i = pos; i <= n; i += lsb(i)){ aib[i] += val; } } int query(int pos){ int ans = 0; pos++; for(int i = pos; i >= 1; i -= lsb(i)){ ans += aib[i]; } return ans; } } set <pair <pii, int>> S; void setInterval(int l, int r, int x){ //cout << 1 << endl; vt <pair <pii, int>> toErase; vt <pair <pii, int>> toInsert; toInsert.pb({{l, r}, x}); for(auto it = S.lb({{l, 0}, 0}); it != S.end() && (*it).fr.fr <= r; it++){ pair <pii, int> obj = (*it); toErase.pb(obj); if(obj.fr.sc > r){ pair <pii, int> newObj = {{r + 1, obj.fr.sc}, obj.sc}; toInsert.pb(newObj); } } auto it = S.lb({{l, 0}, 0}); if(!S.empty() && it != S.begin()){ it--; pair <pii, int> obj = (*it); if(obj.fr.fr < l && obj.fr.sc >= l){ toErase.pb(obj); toInsert.pb({{obj.fr.fr, l - 1}, obj.sc}); if(obj.fr.sc > r){ toInsert.pb({{r + 1, obj.fr.sc}, obj.sc}); } } } for(auto x : toErase){ if(S.find(x) != S.end()){ S.erase(x); } AIB::update(x.sc, -(x.fr.sc - x.fr.fr + 1)); } for(auto x : toInsert){ S.insert(x); AIB::update(x.sc, +(x.fr.sc - x.fr.fr + 1)); } //cout << 2 << endl; } void update(int a, int b, int x){ while(id[a] != id[b]){ if(lvl[head[id[a]]] > lvl[head[id[b]]]){ setInterval(pos[head[id[a]]], pos[a], x); a = par[head[id[a]]]; }else{ setInterval(pos[head[id[b]]], pos[b], x); b = par[head[id[b]]]; } } setInterval(min(pos[a], pos[b]), max(pos[a], pos[b]), x); } void solve(){ int n, m, q; fin >> n >> m >> q; for(int i = 1; i <= n - 1; i++){ int a, b; fin >> a >> b; adj[a].pb(b); adj[b].pb(a); } FOR(1, m){ fin >> c[i]; } //cout << 3 << endl; FOR(1, q){ int x, y; fin >> x >> y; quer[y].pb({x, i}); } //cout << 3 << endl; expl(1, 0); //cout << 3 << endl; hvFirst(1, 0); //cout << 3 << endl; AIB::init(m); //cout << 3 << endl; FOR(1, Id){ S.insert({{pos[head[i]], pos[last[i]]}, 0}); AIB::update(0, pos[last[i]] - pos[head[i]] + 1); } FOR(1, m){ if(i > 1){ update(c[i - 1], c[i], i - 1); } update(c[i], c[i], i); for(pii x : quer[i]){ Ans[x.sc] += AIB::query(m) - AIB::query(x.fr - 1); } } for(int i = 1; i <= q; i++){ fout << Ans[i] << '\n'; } } signed main(){ ios_base::sync_with_stdio(false); fin.tie(0); int T; //fin >> T; T = 1; while(T--){ solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...