oj.uz

답안 #743847

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
743847 2023-05-18T05:07:27 Z hafo Regions (IOI09_regions) C++14
50 / 100
 4011 ms 36892 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], mp[sz];
vector<int> g[maxn], tp[maxn], cp[m], large;
bool fir[maxn];

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

    for(auto v:g[u]) {
        if(v == par) continue;
        if(!mp[home[v]]) fir[v] = 1;
        mp[home[v]]++;
        dfs(v, u);
        mp[home[v]]--;
    }
    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);
    }

    mp[home[1]]++;
    fir[1] = 1;
    for(int i = 1; i <= n; i++)
        if(cnt[home[i]] <= sz) tp[home[i]].pb(i);
    for(int i = 1; i <= r; i++)
        if(cnt[i] > sz) large.pb(i);
    dfs(1, 0);
    while(q--) {
        cin>>r1>>r2;
        assert(r1 != r2);
        if(cnt[r1] <= sz) {
            int ans = 0;
            for(auto u:tp[r1]) {
                ans += get(st[u], en[u], r2) - (r1 == 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++) f[i][home[u]] += mp[large[i]];
      |                    ~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10192 KB Output is correct
2 Correct 5 ms 10320 KB Output is correct
3 Correct 8 ms 10248 KB Output is correct
4 Correct 11 ms 10320 KB Output is correct
5 Correct 15 ms 10264 KB Output is correct
6 Correct 23 ms 10320 KB Output is correct
7 Correct 34 ms 10320 KB Output is correct
8 Correct 35 ms 10448 KB Output is correct
9 Correct 55 ms 10960 KB Output is correct
10 Correct 98 ms 10884 KB Output is correct
11 Correct 140 ms 11196 KB Output is correct
12 Correct 139 ms 11684 KB Output is correct
13 Correct 171 ms 11344 KB Output is correct
14 Correct 217 ms 11856 KB Output is correct
15 Correct 296 ms 15696 KB Output is correct

Subtask #2
35.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1453 ms 15312 KB Output is correct
2 Correct 2190 ms 13768 KB Output is correct
3 Correct 2988 ms 17608 KB Output is correct
4 Correct 282 ms 12104 KB Output is correct
5 Correct 347 ms 14364 KB Output is correct
6 Incorrect 385 ms 15168 KB Output isn't correct
7 Incorrect 1724 ms 14920 KB Output isn't correct
8 Incorrect 1190 ms 25640 KB Output isn't correct
9 Correct 2250 ms 20520 KB Output is correct
10 Incorrect 3540 ms 30860 KB Output isn't correct
11 Correct 4011 ms 20036 KB Output is correct
12 Incorrect 1396 ms 21192 KB Output isn't correct
13 Incorrect 1948 ms 21960 KB Output isn't correct
14 Incorrect 2175 ms 23056 KB Output isn't correct
15 Incorrect 3209 ms 28048 KB Output isn't correct
16 Incorrect 2587 ms 36892 KB Output isn't correct
17 Incorrect 2895 ms 36524 KB Output isn't correct