제출 #427762

#제출 시각아이디문제언어결과실행 시간메모리
427762OdaveyRegions (IOI09_regions)C++17
5 / 100
509 ms6872 KiB
// // ~oisín~ C++ Template // #include <bits/stdc++.h> #define MX_N 5001 #define mp make_pair #define mod7 1000000007 #define modpi 314159 #define PI 3.141592653589793238 #define pb push_back #define FastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define All(a) a.begin(),a.end() #define fi first #define se second #define ll long long int #define ull unsigned long long int int kx[8] = {+2, +2, -2, -2, +1, +1, -1, -1}; int ky[8] = {+1, -1, +1, -1, +2, -2, +2, -2}; int d9x[9] = {+1, +1, +1, +0, +0, +0, -1, -1, -1}; int d9y[9] = {+1, +0, -1, +1, +0, -1, +1, +0, -1}; int dx4[4] = {+0, +0, +1, -1}; int dy4[4] = {+1, -1, +0, +0}; ll gcd(ull a, ull b){ return (a==0)?b:gcd(b%a,a); } ll lcm(ull a, ull b){ return a*(b/gcd(a,b)); } const long long INF = 1e18; using namespace std; int N, R, Q; int H[MX_N]; int p[MX_N]; vector<int> adj[MX_N]; vector<int> r[MX_N]; vector<pair<int, bool> > ord; void dfs(int at){ ord.pb({at, 0}); r[H[at]].pb((int)ord.size()-1); for(int to : adj[at]){ if(p[at] == to){ continue; } dfs(to); } ord.pb({at, 1}); r[H[at]].pb((int)ord.size()-1); } map<pair<int, int>, int> cache; int main(){ cin >> N >> R >> Q; // int c = sqrt(N); int c = 1; cin >> H[0]; --H[0]; for(int i=1;i<N;++i){ cin >> p[i] >> H[i]; --p[i], --H[i]; adj[p[i]].pb(i); } dfs(0); // for(auto p : ord){ // cout << p.fi+1 << ' '; // } // cout << endl; for(int j=0;j<R;++j){ if((int)r[j].size() >= c){ for(int i=0;i<R;++i){ if(i == j){ continue; } //cout << "i & j = " << i+1 << " & " << j+1 << endl; vector<int> tmp; for(auto P : r[i]){ //cout << P << ' '; tmp.pb(P); } //cout << endl; for(auto P : r[j]){ //cout << P << ' '; tmp.pb(P); } sort(All(tmp)); int cntA = 0, cntB = 0; int ans = 0; for(auto ii : tmp){ auto P = ord[ii]; if(H[P.fi] == i){ if(P.se == 0){ ++cntA; //ans += cntB; }else{ --cntA; } }else{ if(P.se == 0){ ++cntB; ans += cntA; }else{ --cntB; } } } //cout << "\nans = " << ans << endl; cache[make_pair(i, j)] = ans; } } } //cout << "Again, but backwards:\n"; for(int i=0;i<R;++i){ if((int)r[i].size() >= c){ for(int j=0;j<R;++j){ if(i == j){ continue; } //cout << "i & j = " << i+1 << " & " << j+1 << endl; vector<int> tmp; for(auto P : r[i]){ //cout << P << ' '; tmp.pb(P); } //cout << endl; for(auto P : r[j]){ //cout << P << ' '; tmp.pb(P); } sort(All(tmp)); int cntA = 0, cntB = 0; int ans = 0; for(auto ii : tmp){ auto P = ord[ii]; if(H[P.fi] == i){ if(P.se == 0){ ++cntA; //ans += cntB; }else{ --cntA; } }else{ if(P.se == 0){ ++cntB; ans += cntA; }else{ --cntB; } } } //cout << "\nans = " << ans << endl; cache[make_pair(i, j)] = ans; } } } // for(int i=0;i<R;++i){ // for(int x : r[i]){ // cout << x << ' '; // } // cout << endl; // } while(Q--){ int r1, r2; cin >> r1 >> r2; --r1, --r2; if((int)r[r1].size() >= c){ cout << cache[make_pair(r1, r2)] << endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...