oj.uz

Submission #427767

# Submission time Handle Problem Language Result Execution time Memory
427767 2021-06-14T21:55:56 Z Odavey Regions (IOI09_regions) C++17
21 / 100
 8000 ms 117140 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 = 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(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();
        }
    }
}

Subtask #1
11.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5 ms 9672 KB Time limit exceeded (wall clock)
2 Execution timed out 6 ms 9672 KB Time limit exceeded (wall clock)
3 Execution timed out 6 ms 9672 KB Time limit exceeded (wall clock)
4 Correct 13 ms 9800 KB Output is correct
5 Correct 23 ms 9928 KB Output is correct
6 Execution timed out 60 ms 11056 KB Time limit exceeded (wall clock)
7 Correct 90 ms 10468 KB Output is correct
8 Correct 159 ms 10688 KB Output is correct
9 Correct 480 ms 12096 KB Output is correct
10 Correct 1146 ms 12776 KB Output is correct
11 Correct 1198 ms 12100 KB Output is correct
12 Correct 2729 ms 14152 KB Output is correct
13 Correct 2374 ms 12972 KB Output is correct
14 Correct 1936 ms 12852 KB Output is correct
15 Correct 3518 ms 16756 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 6403 ms 17308 KB Output is correct
2 Correct 7213 ms 15724 KB Output is correct
3 Execution timed out 8085 ms 20040 KB Time limit exceeded
4 Execution timed out 8093 ms 67172 KB Time limit exceeded
5 Execution timed out 8101 ms 86020 KB Time limit exceeded
6 Runtime error 143 ms 67808 KB Execution killed with signal 11
7 Runtime error 164 ms 70116 KB Execution killed with signal 11
8 Runtime error 192 ms 84780 KB Execution killed with signal 11
9 Runtime error 247 ms 83752 KB Execution killed with signal 11
10 Runtime error 263 ms 97808 KB Execution killed with signal 11
11 Runtime error 274 ms 83048 KB Execution killed with signal 11
12 Runtime error 278 ms 86692 KB Execution killed with signal 11
13 Runtime error 286 ms 88152 KB Execution killed with signal 11
14 Runtime error 310 ms 87248 KB Execution killed with signal 11
15 Runtime error 285 ms 98980 KB Execution killed with signal 11
16 Runtime error 296 ms 117140 KB Execution killed with signal 11
17 Runtime error 297 ms 114328 KB Execution killed with signal 11