oj.uz

Submission #427766

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

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 12 ms 9800 KB Output is correct
5 Correct 24 ms 9928 KB Output is correct
6 Execution timed out 51 ms 11044 KB Time limit exceeded (wall clock)
7 Correct 79 ms 10488 KB Output is correct
8 Correct 145 ms 10788 KB Output is correct
9 Correct 532 ms 12180 KB Output is correct
10 Correct 1164 ms 12724 KB Output is correct
11 Correct 1231 ms 12152 KB Output is correct
12 Correct 2761 ms 14008 KB Output is correct
13 Correct 2451 ms 12876 KB Output is correct
14 Correct 2013 ms 12560 KB Output is correct
15 Correct 3582 ms 16780 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 6249 ms 17088 KB Output is correct
2 Correct 7979 ms 15824 KB Output is correct
3 Execution timed out 8048 ms 20036 KB Time limit exceeded
4 Execution timed out 8035 ms 66576 KB Time limit exceeded
5 Execution timed out 8093 ms 84656 KB Time limit exceeded
6 Runtime error 151 ms 67616 KB Execution killed with signal 11
7 Runtime error 175 ms 70148 KB Execution killed with signal 11
8 Runtime error 192 ms 84768 KB Execution killed with signal 11
9 Runtime error 251 ms 83804 KB Execution killed with signal 11
10 Runtime error 271 ms 97840 KB Execution killed with signal 11
11 Runtime error 300 ms 82968 KB Execution killed with signal 11
12 Runtime error 299 ms 86712 KB Execution killed with signal 11
13 Runtime error 275 ms 88048 KB Execution killed with signal 11
14 Runtime error 297 ms 87332 KB Execution killed with signal 11
15 Runtime error 320 ms 98980 KB Execution killed with signal 11
16 Runtime error 307 ms 117144 KB Execution killed with signal 11
17 Runtime error 308 ms 114448 KB Execution killed with signal 11