제출 #501508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
501508		Joo	Regions (IOI09_regions)	C++17	55 / 100	8054 ms	62284 KiB

regions

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+10, BLOCK = 500, MR = 25010;

int n, R, Q, tin[N], tout[N], sz[N], re[N], cnt[MR], ti;
unordered_map<int, int> ans[MR]; //stores answer for big regions(precompute)
vector<int> lis[MR], G[N], ch[N]; //lis[i] denotes a list of those whose region is i sorted by tin[i]

inline void add(int p, int u){
    ch[p].emplace_back(u);
    cnt[re[u]]++;
}

inline bool isbig(int r){
    return ((int)lis[r].size() > BLOCK);
}

inline bool isAnc(int p, int u){
    return (tin[p] <= tin[u] and tout[u] <= tout[p]);
}

void dfs1(int u){
    sz[u] = 1;
    lis[re[u]].emplace_back(u);

    tin[u] = ++ti;
    for(int v : G[u]) dfs1(v), sz[u] += sz[v];
    tout[u] = ti;
}

void dfs2(int u, bool keep){
    int bc = -1;
    for(int v : G[u]) if(bc == -1 or sz[v] > sz[bc]) bc = v;
    
    for(int v : G[u]) if(v != bc) dfs2(v, 0);
    if(bc != -1){
        dfs2(bc, 1);
        swap(ch[bc], ch[u]);
    }
    
    add(u, u);
    for(int v : G[u]){
        if(v == bc) continue;
        for(int vv : ch[v]){
            add(u, vv);
        }
    }

    if(isbig(re[u])){
        for(int r = 1; r <= R; r++){
            ans[re[u]][r] += cnt[r];
        }
    }

    if(keep == 0){
        for(int v : ch[u]) cnt[re[v]]--;
    }

}

int getans(int r1, int r2){
    int b = 0, s = 0, res = 0;
    stack<int> st;
    while(b < lis[r1].size() or s < lis[r2].size()){
        if((b < lis[r1].size()) and (s == lis[r2].size() or tin[lis[r1][b]] < tin[lis[r2][s]])){
            while(!st.empty() and !isAnc(st.top(), lis[r1][b])) st.pop();
            st.push(lis[r1][b]);

            b++;
        } else {
            while(!st.empty() and !isAnc(st.top(), lis[r2][s])) st.pop();

            res += st.size();
            s++;
        }
    }
    return res;
}

int main(void){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> R >> Q;
    cin >> re[1];
    for(int i = 2; i <= n; i++){
        int p; cin >> p >> re[i];
        G[p].emplace_back(i);
    }

    dfs1(1);
    dfs2(1, 1);

    while(Q--){
        int r1, r2; cin >> r1 >> r2;
        if(isbig(r1) or isbig(r2)){
            cout << ans[r1][r2] << endl;
        } else {
            cout << getans(r1, r2) << endl;
        }
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

regions.cpp: In function 'int getans(int, int)':
regions.cpp:65:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     while(b < lis[r1].size() or s < lis[r2].size()){
      |           ~~^~~~~~~~~~~~~~~~
regions.cpp:65:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     while(b < lis[r1].size() or s < lis[r2].size()){
      |                                 ~~^~~~~~~~~~~~~~~~
regions.cpp:66:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         if((b < lis[r1].size()) and (s == lis[r2].size() or tin[lis[r1][b]] < tin[lis[r2][s]])){
      |             ~~^~~~~~~~~~~~~~~~
regions.cpp:66:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         if((b < lis[r1].size()) and (s == lis[r2].size() or tin[lis[r1][b]] < tin[lis[r2][s]])){
      |                                      ~~^~~~~~~~~~~~~~~~~

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