oj.uz

답안 #743829

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
743829 2023-05-18T04:07:02 Z hafo Regions (IOI09_regions) C++14
0 / 100
 2148 ms 39104 KB 
#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;
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 10192 KB Output isn't correct
2 Incorrect 5 ms 10192 KB Output isn't correct
3 Incorrect 7 ms 10192 KB Output isn't correct
4 Incorrect 11 ms 10264 KB Output isn't correct
5 Incorrect 12 ms 10320 KB Output isn't correct
6 Incorrect 24 ms 10320 KB Output isn't correct
7 Incorrect 36 ms 10320 KB Output isn't correct
8 Incorrect 35 ms 10448 KB Output isn't correct
9 Incorrect 60 ms 10960 KB Output isn't correct
10 Incorrect 90 ms 10868 KB Output isn't correct
11 Incorrect 128 ms 11028 KB Output isn't correct
12 Incorrect 148 ms 11728 KB Output isn't correct
13 Incorrect 213 ms 11216 KB Output isn't correct
14 Incorrect 230 ms 11788 KB Output isn't correct
15 Incorrect 189 ms 16080 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 591 ms 15268 KB Output isn't correct
2 Incorrect 867 ms 13512 KB Output isn't correct
3 Incorrect 1206 ms 17884 KB Output isn't correct
4 Incorrect 291 ms 11908 KB Output isn't correct
5 Incorrect 383 ms 14548 KB Output isn't correct
6 Incorrect 464 ms 13376 KB Output isn't correct
7 Incorrect 608 ms 14416 KB Output isn't correct
8 Incorrect 614 ms 21980 KB Output isn't correct
9 Incorrect 1300 ms 19912 KB Output isn't correct
10 Incorrect 1465 ms 28300 KB Output isn't correct
11 Incorrect 2148 ms 19072 KB Output isn't correct
12 Incorrect 948 ms 20460 KB Output isn't correct
13 Incorrect 1366 ms 21300 KB Output isn't correct
14 Incorrect 1575 ms 20680 KB Output isn't correct
15 Incorrect 1713 ms 27980 KB Output isn't correct
16 Incorrect 1939 ms 39104 KB Output isn't correct
17 Incorrect 1650 ms 36372 KB Output isn't correct