제출 #743829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
743829		hafo	Regions (IOI09_regions)	C++14	0 / 100	2148 ms	39104 KiB

regions

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 7;
const ll oo = 1e18 + 69;
const int sz = 450 + 7;
const int m = 25e3 + 7;

int n, st[maxn], en[maxn], timer = 0, a[maxn], r, q, home[maxn], cnt[maxn], r1, r2, f[sz][m];
vector<int> g[maxn], fir[maxn], cp[m], large;
bool check[maxn];

void dfs(int u, int par) {
    st[u] = ++timer;
    cp[home[u]].pb(timer);
    for(int i = 0; i < large.size(); i++)
    if(check[home[large[i]]]) {
        f[i][home[u]]++;
    }

    for(auto v:g[u]) {
        if(v == par) continue;
        if(!check[home[v]]) {
            check[home[v]] = 1;
            fir[home[v]].pb(v);
            dfs(v, u);
            check[home[v]] = 0;
        } else dfs(v, u);
    }
    en[u] = timer;
}

int get(int l, int r, int col) {
    return upper_bound(all(cp[col]), r) - lower_bound(all(cp[col]), l);
}

int main() {
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>r>>q;
    cin>>home[1];
    cnt[home[1]]++;
    for(int i = 2; i <= n; i++) {
        int x;
        cin>>x>>home[i];
        cnt[home[i]]++;
        g[x].pb(i);
    }

    check[home[1]] = 1;
    fir[home[1]].pb(1);
    for(int i = 1; i <= r; i++)
        if(cnt[r] > sz) large.pb(i);
    dfs(1, 0);

    while(q--) {
        cin>>r1>>r2;
        if(cnt[r1] <= sz) {
            int ans = 0;
            for(auto u:fir[r1]) {
                ans += get(st[u], en[u], r2);
            }
            cout<<ans<<endl;
        } else {
            int id = lower_bound(all(large), r1) - large.begin();
            cout<<f[id][r2]<<endl;
        }
    }
    return 0;
}

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

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i = 0; i < large.size(); i++)
      |                    ~~^~~~~~~~~~~~~~

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