제출 #427762

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
427762		Odavey	Regions (IOI09_regions)	C++17	5 / 100	509 ms	6872 KiB

regions

//
// ~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;
        }
    }
}

• Subtask 1: 5 / 15
• Subtask 2: 0 / 85