Submission #427771

# Submission time Handle Problem Language Result Execution time Memory
427771 2021-06-14T22:03:20 Z Odavey Regions (IOI09_regions) C++17
45 / 100
8000 ms 38596 KB
//
// ~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];
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 cache[5000][5000];

int main(){
    cin >> N >> R >> Q;
    int c = 1000000;
    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;
                }
                vector<int> tmp;
                for(auto P : r[i]){
                    tmp.pb(P);
                }
                for(auto P : r[j]){
                    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;
                        }else{
                            --cntA;
                        }
                    }else{
                        if(P.se == 0){
                            ++cntB;
                            ans += cntA;
                        }else{
                            --cntB;
                        }
                    }
                }
                //cache[make_pair(i, j)] = ans;
                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;
                }
                vector<int> tmp;
                for(auto P : r[i]){
                    tmp.pb(P);
                }
                for(auto P : r[j]){
                    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;
                        }else{
                            --cntA;
                        }
                    }else{
                        if(P.se == 0){
                            ++cntB;
                            ans += cntA;
                        }else{
                            --cntB;
                        }
                    }
                }
                cache[i][j] = ans;
                //cache[make_pair(i, j)] = ans;
            }
        }
    }

    while(Q--){
        int r1, r2;
        cin >> r1 >> r2;
        --r1, --r2;
        if((int)r[r1].size() >= c){
            cout << cache[r1][r2] << endl;
            cout.flush();
        }else{
            vector<int> tmp;
            for(auto P : r[r1]){
                tmp.pb(P);
            }
            for(auto P : r[r2]){
                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] == r1){
                    if(P.se == 0){
                        ++cntA;
                    }else{
                        --cntA;
                    }
                }else{
                    if(P.se == 0){
                        ++cntB;
                        ans += cntA;
                    }else{
                        --cntB;
                    }
                }
            }
            cout << ans << endl;
            cout.flush();
        }
    }
}
# Verdict Execution time Memory Grader output
1 Correct 6 ms 9672 KB Output is correct
2 Correct 6 ms 9672 KB Output is correct
3 Correct 8 ms 9672 KB Output is correct
4 Correct 8 ms 9672 KB Output is correct
5 Correct 14 ms 9672 KB Output is correct
6 Correct 34 ms 9800 KB Output is correct
7 Correct 37 ms 9800 KB Output is correct
8 Correct 46 ms 9800 KB Output is correct
9 Correct 81 ms 10440 KB Output is correct
10 Correct 98 ms 10440 KB Output is correct
11 Correct 148 ms 10668 KB Output is correct
12 Correct 258 ms 11588 KB Output is correct
13 Correct 267 ms 11036 KB Output is correct
14 Correct 599 ms 11704 KB Output is correct
15 Correct 809 ms 15900 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 8068 ms 16564 KB Time limit exceeded
2 Execution timed out 8080 ms 14764 KB Time limit exceeded
3 Execution timed out 8005 ms 18892 KB Time limit exceeded
4 Correct 410 ms 11708 KB Output is correct
5 Correct 679 ms 14520 KB Output is correct
6 Correct 3228 ms 13296 KB Output is correct
7 Correct 3864 ms 15344 KB Output is correct
8 Correct 3739 ms 22000 KB Output is correct
9 Correct 5527 ms 22704 KB Output is correct
10 Execution timed out 8054 ms 29608 KB Time limit exceeded
11 Execution timed out 8032 ms 21020 KB Time limit exceeded
12 Execution timed out 8061 ms 23328 KB Time limit exceeded
13 Execution timed out 8089 ms 23944 KB Time limit exceeded
14 Execution timed out 8084 ms 23400 KB Time limit exceeded
15 Execution timed out 8079 ms 28968 KB Time limit exceeded
16 Execution timed out 8037 ms 38596 KB Time limit exceeded
17 Execution timed out 8085 ms 36524 KB Time limit exceeded