Submission #427789

#	Time	Username	Problem	Language	Result	Execution time	Memory
427789		Odavey	Regions (IOI09_regions)	C++17	16 / 100	8066 ms	66916 KiB

regions

//
// ~oisín~ C++ Template
//

#include                <bits/stdc++.h>
#define MX_N            200005
#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], p[MX_N];
vector<int> adj[MX_N], r[25001];
vector<pair<int, bool> > ord;
map<int, int> cache[25001];

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);
}

int main(){
    cin >> N >> R >> Q;
//    int c = sqrt(N);
    int c = 1000000000;
    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(int j=0;j<R;++j){
        if((int)r[j].size() >= c){
            for(int i=0;i<R;++i){
                if(i == j){
                    continue;
                }
                int x = 0, y = 0;
                int cur;
                if(r[i][0] < r[j][0]){
                    cur = r[i][0];
                    ++x;
                }else{
                    cur = r[j][0];
                    ++y;
                }
                int cntA = 0, cntB = 0;
                int ans = 0;
                while(true){
                    auto P = ord[cur];
                    if(H[P.fi] == i){
                        if(P.se == 0){
                            ++cntA;
                        }else{
                            --cntA;
                        }
                    }else{
                        if(P.se == 0){
                            ++cntB;
                            ans += cntA;
                        }else{
                            --cntB;
                        }
                    }
                    if(x == (int)r[i].size() && y == (int)r[j].size()){
                        break;
                    }else if(x == (int)r[i].size()){
                        cur = r[j][y];
                        ++y;
                    }else if(y == (int)r[j].size()){
                        cur = r[i][x];
                        ++x;
                    }else{
                        if(r[i][x] < r[j][y]){
                            cur = r[i][x];
                            ++x;
                        }else{
                            cur = r[j][y];
                            ++y;
                        }
                    }
                }
                cache[i][j] = ans;
            }
        }
    }

    for(int i=0;i<R;++i){
        if((int)r[i].size() >= c){
            for(int j=0;j<R;++j){
                if(i == j){
                    continue;
                }
                int x = 0, y = 0;
                int cur;
                if(r[i][0] < r[j][0]){
                    cur = r[i][0];
                    ++x;
                }else{
                    cur = r[j][0];
                    ++y;
                }
                int cntA = 0, cntB = 0;
                int ans = 0;
                while(true){
                    auto P = ord[cur];
                    if(H[P.fi] == i){
                        if(P.se == 0){
                            ++cntA;
                        }else{
                            --cntA;
                        }
                    }else{
                        if(P.se == 0){
                            ++cntB;
                            ans += cntA;
                        }else{
                            --cntB;
                        }
                    }
                    if(x == (int)r[i].size() && y == (int)r[j].size()){
                        break;
                    }else if(x == (int)r[i].size()){
                        cur = r[j][y];
                        ++y;
                    }else if(y == (int)r[j].size()){
                        cur = r[i][x];
                        ++x;
                    }else{
                        if(r[i][x] < r[j][y]){
                            cur = r[i][x];
                            ++x;
                        }else{
                            cur = r[j][y];
                            ++y;
                        }
                    }
                }
                cache[i][j] = ans;
            }
        }
    }

    while(Q--){
        int r1, r2;
        cin >> r1 >> r2;
        --r1, --r2;
        if((int)r[r1].size() >= c || (int)r[r2].size() >= c){
            cout << cache[r1][r2] << endl;
            cout.flush();
        }else{
            int x = 0, y = 0;
            int cur;
            if(r[r1][0] < r[r2][0]){
                cur = r[r1][0];
                ++x;
            }else{
                cur = r[r2][0];
                ++y;
            }
            int cntA = 0, cntB = 0;
            int ans = 0;
            while(true){
                auto P = ord[cur];
                if(H[P.fi] == r1){
                    if(P.se == 0){
                        ++cntA;
                    }else{
                        --cntA;
                    }
                }else{
                    if(P.se == 0){
                        ++cntB;
                        ans += cntA;
                    }else{
                        --cntB;
                    }
                }
                if(x == (int)r[r1].size() && y == (int)r[r2].size()){
                    break;
                }else if(x == (int)r[r1].size()){
                    cur = r[r2][y];
                    ++y;
                }else if(y == (int)r[r2].size()){
                    cur = r[r1][x];
                    ++x;
                }else{
                    if(r[r1][x] < r[r2][y]){
                        cur = r[r1][x];
                        ++x;
                    }else{
                        cur = r[r2][y];
                        ++y;
                    }
                }
            }
            cout << ans << endl;
            cout.flush();
        }
    }
}

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