Submission #427784

#	Time	Username	Problem	Language	Result	Execution time	Memory
427784		Odavey	Regions (IOI09_regions)	C++17	26 / 100	2695 ms	95324 KiB

regions

//
// ~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];
map<int, int> cache[MX_N];

int main(){
    cin >> N >> R >> Q;
    int c = sqrt(N);
//    int c = 1000000000;
    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;
                }
                int x = 0, y = 0;
                int cur;
                if(r[i][0] < r[j][0]){
                    cur = r[i][0];
                    ++x;
                }else{
                    cur = r[j][0];
                    ++y;
                }
                int cntA = 0, cntB = 0;
                int ans = 0;
                while(true){
                    auto P = ord[cur];
                    if(H[P.fi] == i){
                        if(P.se == 0){
                            ++cntA;
                        }else{
                            --cntA;
                        }
                    }else{
                        if(P.se == 0){
                            ++cntB;
                            ans += cntA;
                        }else{
                            --cntB;
                        }
                    }
                    if(x == r[i].size() && y == r[j].size()){
                        break;
                    }else if(x == r[i].size()){
                        cur = r[j][y];
                        ++y;
                    }else if(y == r[j].size()){
                        cur = r[i][x];
                        ++x;
                    }else{
                        if(r[i][x] < r[j][y]){
                            cur = r[i][x];
                            ++x;
                        }else{
                            cur = r[j][y];
                            ++y;
                        }
                    }
                }
                cache[i][j] = ans;
                //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;
                }
                int x = 0, y = 0;
                int cur;
                if(r[i][0] < r[j][0]){
                    cur = r[i][0];
                    ++x;
                }else{
                    cur = r[j][0];
                    ++y;
                }
                int cntA = 0, cntB = 0;
                int ans = 0;
                while(true){
                    auto P = ord[cur];
                    if(H[P.fi] == i){
                        if(P.se == 0){
                            ++cntA;
                        }else{
                            --cntA;
                        }
                    }else{
                        if(P.se == 0){
                            ++cntB;
                            ans += cntA;
                        }else{
                            --cntB;
                        }
                    }
                    if(x == r[i].size() && y == r[j].size()){
                        break;
                    }else if(x == r[i].size()){
                        cur = r[j][y];
                        ++y;
                    }else if(y == r[j].size()){
                        cur = r[i][x];
                        ++x;
                    }else{
                        if(r[i][x] < r[j][y]){
                            cur = r[i][x];
                            ++x;
                        }else{
                            cur = r[j][y];
                            ++y;
                        }
                    }
                }
                cache[i][j] = ans;
                //cache[make_pair(i, j)] = ans;
//                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 || (int)r[r2].size() >= c){
//            cout << cache[make_pair(r1, r2)] << endl;
            cout << cache[r1][r2] << endl;
            cout.flush();
        }else{
            int x = 0, y = 0;
            int cur;
            if(r[r1][0] < r[r2][0]){
                cur = r[r1][0];
                ++x;
            }else{
                cur = r[r2][0];
                ++y;
            }
            int cntA = 0, cntB = 0;
            int ans = 0;
            while(true){
                auto P = ord[cur];
                if(H[P.fi] == r1){
                    if(P.se == 0){
                        ++cntA;
                    }else{
                        --cntA;
                    }
                }else{
                    if(P.se == 0){
                        ++cntB;
                        ans += cntA;
                    }else{
                        --cntB;
                    }
                }
                if(x == r[r1].size() && y == r[r2].size()){
                    break;
                }else if(x == r[r1].size()){
                    cur = r[r2][y];
                    ++y;
                }else if(y == r[r2].size()){
                    cur = r[r1][x];
                    ++x;
                }else{
                    if(r[r1][x] < r[r2][y]){
                        cur = r[r1][x];
                        ++x;
                    }else{
                        cur = r[r2][y];
                        ++y;
                    }
                }
            }
            cout << ans << endl;
            cout.flush();
        }
    }
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:108:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |                     if(x == r[i].size() && y == r[j].size()){
      |                        ~~^~~~~~~~~~~~~~
regions.cpp:108:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |                     if(x == r[i].size() && y == r[j].size()){
      |                                            ~~^~~~~~~~~~~~~~
regions.cpp:110:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |                     }else if(x == r[i].size()){
      |                              ~~^~~~~~~~~~~~~~
regions.cpp:113:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |                     }else if(y == r[j].size()){
      |                              ~~^~~~~~~~~~~~~~
regions.cpp:166:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |                     if(x == r[i].size() && y == r[j].size()){
      |                        ~~^~~~~~~~~~~~~~
regions.cpp:166:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |                     if(x == r[i].size() && y == r[j].size()){
      |                                            ~~^~~~~~~~~~~~~~
regions.cpp:168:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |                     }else if(x == r[i].size()){
      |                              ~~^~~~~~~~~~~~~~
regions.cpp:171:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |                     }else if(y == r[j].size()){
      |                              ~~^~~~~~~~~~~~~~
regions.cpp:258:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  258 |                 if(x == r[r1].size() && y == r[r2].size()){
      |                    ~~^~~~~~~~~~~~~~~
regions.cpp:258:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  258 |                 if(x == r[r1].size() && y == r[r2].size()){
      |                                         ~~^~~~~~~~~~~~~~~
regions.cpp:260:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  260 |                 }else if(x == r[r1].size()){
      |                          ~~^~~~~~~~~~~~~~~
regions.cpp:263:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  263 |                 }else if(y == r[r2].size()){
      |                          ~~^~~~~~~~~~~~~~~

• Subtask 1: 11 / 15
• Subtask 2: 15 / 85