답안 #427762

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
427762 2021-06-14T21:43:15 Z Odavey Regions (IOI09_regions) C++17
5 / 100
509 ms 6872 KB
//
// ~oisín~ C++ Template
//

#include                <bits/stdc++.h>
#define MX_N            5001
#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 = sqrt(N);
    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(auto p : ord){
//        cout << p.fi+1 << ' ';
//    }
//    cout << endl;

    for(int j=0;j<R;++j){
        if((int)r[j].size() >= c){
            for(int i=0;i<R;++i){
                if(i == j){
                    continue;
                }
                //cout << "i & j = " << i+1 << " & " << j+1 << endl;
                vector<int> tmp;
                for(auto P : r[i]){
                    //cout << P << ' ';
                    tmp.pb(P);
                }
                //cout << endl;
                for(auto P : r[j]){
                    //cout << P << ' ';
                    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;
                            //ans += cntB;
                        }else{
                            --cntA;
                        }
                    }else{
                        if(P.se == 0){
                            ++cntB;
                            ans += cntA;
                        }else{
                            --cntB;
                        }
                    }
                }
                //cout << "\nans = " << ans << endl;
                cache[make_pair(i, j)] = ans;
            }
        }
    }

    //cout << "Again, but backwards:\n";
    for(int i=0;i<R;++i){
        if((int)r[i].size() >= c){
            for(int j=0;j<R;++j){
                if(i == j){
                    continue;
                }
                //cout << "i & j = " << i+1 << " & " << j+1 << endl;
                vector<int> tmp;
                for(auto P : r[i]){
                    //cout << P << ' ';
                    tmp.pb(P);
                }
                //cout << endl;
                for(auto P : r[j]){
                    //cout << P << ' ';
                    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;
                            //ans += cntB;
                        }else{
                            --cntA;
                        }
                    }else{
                        if(P.se == 0){
                            ++cntB;
                            ans += cntA;
                        }else{
                            --cntB;
                        }
                    }
                }
                //cout << "\nans = " << ans << endl;
                cache[make_pair(i, j)] = ans;
            }
        }
    }

//    for(int i=0;i<R;++i){
//        for(int x : r[i]){
//            cout << x << ' ';
//        }
//        cout << endl;
//    }

    while(Q--){
        int r1, r2;
        cin >> r1 >> r2;
        --r1, --r2;
        if((int)r[r1].size() >= c){
            cout << cache[make_pair(r1, r2)] << endl;
        }
    }
}
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1 ms 456 KB Time limit exceeded (wall clock)
2 Execution timed out 1 ms 456 KB Time limit exceeded (wall clock)
3 Execution timed out 1 ms 456 KB Time limit exceeded (wall clock)
4 Correct 9 ms 584 KB Output is correct
5 Correct 11 ms 584 KB Output is correct
6 Execution timed out 67 ms 4420 KB Time limit exceeded (wall clock)
7 Correct 119 ms 1996 KB Output is correct
8 Correct 148 ms 3144 KB Output is correct
9 Correct 509 ms 6872 KB Output is correct
10 Runtime error 5 ms 1352 KB Execution killed with signal 11
11 Runtime error 4 ms 1352 KB Execution killed with signal 11
12 Runtime error 7 ms 1480 KB Execution killed with signal 11
13 Runtime error 5 ms 1096 KB Execution killed with signal 11
14 Runtime error 5 ms 1400 KB Execution killed with signal 11
15 Runtime error 5 ms 1224 KB Execution killed with signal 11
# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 1540 KB Execution killed with signal 11
2 Runtime error 5 ms 1452 KB Execution killed with signal 11
3 Runtime error 5 ms 1152 KB Execution killed with signal 11
4 Runtime error 5 ms 1352 KB Execution killed with signal 11
5 Runtime error 4 ms 1192 KB Execution killed with signal 11
6 Runtime error 5 ms 1196 KB Execution killed with signal 11
7 Runtime error 7 ms 1352 KB Execution killed with signal 6
8 Runtime error 6 ms 1224 KB Execution killed with signal 11
9 Runtime error 5 ms 1224 KB Execution killed with signal 11
10 Runtime error 5 ms 1224 KB Execution killed with signal 11
11 Runtime error 5 ms 1096 KB Execution killed with signal 11
12 Runtime error 4 ms 1224 KB Execution killed with signal 11
13 Runtime error 5 ms 1224 KB Execution killed with signal 11
14 Runtime error 6 ms 1096 KB Execution killed with signal 11
15 Runtime error 6 ms 1224 KB Execution killed with signal 11
16 Runtime error 5 ms 1224 KB Execution killed with signal 11
17 Runtime error 5 ms 1224 KB Execution killed with signal 11