oj.uz

Submission #175985

# Submission time Handle Problem Language Result Execution time Memory
175985 2020-01-07T13:28:56 Z stefdasca Regions (IOI09_regions) C++14
80 / 100
 8000 ms 90336 KB 
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

// #define fisier

using namespace std;

typedef long long ll;


int add(int a, int b)
{
    ll x = a+b;
    if(x >= mod)
        x -= mod;
    if(x < 0)
        x += mod;
    return x;
}
ll mul(ll a, ll b)
{
    return (a*b) % mod;
}

ll pw(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

int n, r, q, sr[25002], st[200002], dr[200002], reg[200002], m, nd[200002], sz[25002];

pair<int, int> bst[25002];

int iz[25002];

vector<int> v[200002];

vector<int> ap[25002];

int wh[1002];
int ans[1002][25002];
int crr = 0;

void dfs(int nod, int above)
{
    ans[crr][reg[nod]] += above;
    above += (reg[nod] == wh[crr]);
    for(int i = 0; i < v[nod].size(); ++i)
    {
        int vecin = v[nod][i];
        dfs(vecin, above);
    }
}

void dfs2(int nod)
{
    ++m;
    st[nod] = m;
    nd[m] = nod;
    ap[reg[nod]].pb(m);
    for(int i = 0; i < v[nod].size(); ++i)
    {
        int vecin = v[nod][i];
        dfs2(vecin);
    }
    dr[nod] = m;
}

int cb(int area, int mx)
{
    int st = 0;
    int dr = ap[area].size() - 1;
    int ans = -1;
    while(st <= dr)
    {
        int mid = (st + dr) / 2;
        if(ap[area][mid] <= mx)
            ans = mid, st = mid + 1;
        else
            dr = mid - 1;
    }
    return (ans + 1);
}
int solve(int ra, int rb)
{
    int ans = 0;
    for(int i = 0; i < ap[ra].size(); ++i)
    {
        int nod = nd[ap[ra][i]];
        ans += cb(rb, dr[nod]) - cb(rb, st[nod] - 1);
    }
    return ans;
}
int main()
{

    #ifdef fisier
        ifstream f("input.in");
        ofstream g("output.out");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> r >> q;
    for(int i = 1; i <= n; ++i)
    {
        if(i > 1)
        {
            int tt;
            cin >> tt >> reg[i];
            v[tt].pb(i);
        }
        else
            cin >> reg[i];
        sz[reg[i]]++;
    }
    for(int i = 1; i <= r; ++i)
        bst[i] = {sz[i], i};
    sort(bst + 1, bst + r + 1);
    for(int i = r; i >= max(1, r - 699); --i)
    {
        m = 0;
        ++crr;
        iz[bst[i].se] = crr;
        wh[crr] = bst[i].se;
        dfs(1, 0);
    }
    dfs2(1);
    for(int i = 1; i <= q; ++i)
    {
        int a, b;
        cin >> a >> b;
        if(iz[a])
            cout << ans[iz[a]][b] << endl;
        else
            cout << solve(a, b) << endl;
    }
    return 0;
}

Compilation message

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:64:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); ++i)
                    ~~^~~~~~~~~~~~~~~
regions.cpp: In function 'void dfs2(int)':
regions.cpp:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); ++i)
                    ~~^~~~~~~~~~~~~~~
regions.cpp: In function 'int solve(int, int)':
regions.cpp:103:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ap[ra].size(); ++i)
                    ~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5752 KB Output is correct
2 Correct 8 ms 5752 KB Output is correct
3 Correct 9 ms 5752 KB Output is correct
4 Correct 12 ms 5880 KB Output is correct
5 Correct 16 ms 5880 KB Output is correct
6 Correct 29 ms 7036 KB Output is correct
7 Correct 37 ms 6520 KB Output is correct
8 Correct 44 ms 6776 KB Output is correct
9 Correct 49 ms 7672 KB Output is correct
10 Correct 187 ms 8616 KB Output is correct
11 Correct 215 ms 7928 KB Output is correct
12 Correct 396 ms 9532 KB Output is correct
13 Correct 451 ms 8492 KB Output is correct
14 Correct 374 ms 8160 KB Output is correct
15 Correct 296 ms 10016 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1202 ms 10872 KB Output is correct
2 Correct 1397 ms 10128 KB Output is correct
3 Correct 1693 ms 12664 KB Output is correct
4 Correct 789 ms 21060 KB Output is correct
5 Correct 725 ms 24996 KB Output is correct
6 Correct 1781 ms 30528 KB Output is correct
7 Correct 2763 ms 39756 KB Output is correct
8 Correct 1982 ms 43228 KB Output is correct
9 Correct 6921 ms 58372 KB Output is correct
10 Correct 3897 ms 86496 KB Output is correct
11 Execution timed out 8015 ms 75888 KB Time limit exceeded
12 Execution timed out 8048 ms 32116 KB Time limit exceeded
13 Execution timed out 8013 ms 62612 KB Time limit exceeded
14 Execution timed out 8029 ms 39244 KB Time limit exceeded
15 Correct 5718 ms 87508 KB Output is correct
16 Correct 3858 ms 90336 KB Output is correct
17 Correct 3928 ms 78956 KB Output is correct