Submission #175985

#	Time	Username	Problem	Language	Result	Execution time	Memory
175985		stefdasca	Regions (IOI09_regions)	C++14	80 / 100	8048 ms	90336 KiB

regions

#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 (stderr)

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 / 15
• Subtask 2: 65 / 85