oj.uz

Submission #427765

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

    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[make_pair(i, j)] = ans;
            }
        }
    }

    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
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 5 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 9672 KB Output is correct
5 Correct 24 ms 9852 KB Output is correct
6 Execution timed out 73 ms 13608 KB Time limit exceeded (wall clock)
7 Correct 104 ms 11084 KB Output is correct
8 Correct 180 ms 12200 KB Output is correct
9 Correct 525 ms 16044 KB Output is correct
10 Correct 1287 ms 21348 KB Output is correct
11 Correct 1289 ms 15228 KB Output is correct
12 Correct 2942 ms 24068 KB Output is correct
13 Correct 2569 ms 18140 KB Output is correct
14 Correct 2113 ms 14144 KB Output is correct
15 Correct 3607 ms 19236 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 6569 ms 18640 KB Output is correct
2 Correct 7918 ms 17640 KB Output is correct
3 Execution timed out 8052 ms 22796 KB Time limit exceeded
4 Runtime error 2833 ms 131076 KB Execution killed with signal 9
5 Runtime error 3001 ms 131076 KB Execution killed with signal 9
6 Runtime error 2251 ms 131076 KB Execution killed with signal 9
7 Runtime error 2910 ms 131076 KB Execution killed with signal 9
8 Runtime error 3349 ms 131076 KB Execution killed with signal 9
9 Runtime error 3399 ms 131076 KB Execution killed with signal 9
10 Runtime error 1873 ms 131076 KB Execution killed with signal 9
11 Runtime error 2197 ms 131076 KB Execution killed with signal 9
12 Runtime error 3827 ms 131076 KB Execution killed with signal 9
13 Runtime error 3844 ms 131076 KB Execution killed with signal 9
14 Runtime error 5717 ms 131076 KB Execution killed with signal 9
15 Runtime error 3164 ms 131076 KB Execution killed with signal 9
16 Runtime error 2818 ms 131076 KB Execution killed with signal 9
17 Runtime error 5276 ms 131076 KB Execution killed with signal 9