oj.uz

답안 #743828

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
743828 2023-05-18T04:05:14 Z hafo Regions (IOI09_regions) C++14
0 / 100
 2362 ms 39044 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<<"\n";
        } else {
            int id = lower_bound(all(large), r1) - large.begin();
            cout<<f[id][r2]<<"\n";
        }
    }
    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 9 ms 10288 KB Output isn't correct
2 Incorrect 10 ms 10276 KB Output isn't correct
3 Incorrect 7 ms 10308 KB Output isn't correct
4 Incorrect 14 ms 10328 KB Output isn't correct
5 Incorrect 14 ms 10320 KB Output isn't correct
6 Incorrect 27 ms 10324 KB Output isn't correct
7 Incorrect 29 ms 10448 KB Output isn't correct
8 Incorrect 45 ms 10396 KB Output isn't correct
9 Incorrect 60 ms 10960 KB Output isn't correct
10 Incorrect 94 ms 10832 KB Output isn't correct
11 Incorrect 141 ms 11104 KB Output isn't correct
12 Incorrect 143 ms 11660 KB Output isn't correct
13 Incorrect 186 ms 11216 KB Output isn't correct
14 Incorrect 199 ms 11820 KB Output isn't correct
15 Incorrect 215 ms 16072 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 866 ms 15260 KB Output isn't correct
2 Incorrect 1040 ms 13388 KB Output isn't correct
3 Incorrect 872 ms 17860 KB Output isn't correct
4 Incorrect 247 ms 11984 KB Output isn't correct
5 Incorrect 366 ms 14536 KB Output isn't correct
6 Incorrect 350 ms 13340 KB Output isn't correct
7 Incorrect 584 ms 14304 KB Output isn't correct
8 Incorrect 703 ms 22076 KB Output isn't correct
9 Incorrect 1421 ms 19904 KB Output isn't correct
10 Incorrect 1683 ms 28200 KB Output isn't correct
11 Incorrect 2362 ms 19096 KB Output isn't correct
12 Incorrect 1004 ms 20516 KB Output isn't correct
13 Incorrect 1212 ms 21280 KB Output isn't correct
14 Incorrect 1520 ms 20656 KB Output isn't correct
15 Incorrect 1750 ms 27984 KB Output isn't correct
16 Incorrect 1417 ms 39044 KB Output isn't correct
17 Incorrect 1992 ms 36452 KB Output isn't correct