oj.uz

Submission #175991

# Submission time Handle Problem Language Result Execution time Memory
175991 2020-01-07T13:44:52 Z stefdasca Regions (IOI09_regions) C++14
100 / 100
 6561 ms 119716 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;

int above[1002];
void dfs(int nod)
{
    for(int i = 1; i <= min(r, 1000); ++i)
        ans[i][reg[nod]] += above[i];
    above[iz[reg[nod]]]++;
    for(int i = 0; i < v[nod].size(); ++i)
    {
        int vecin = v[nod][i];
        dfs(vecin);
    }
    above[iz[reg[nod]]]--;
}

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 - 999); --i)
    {
        m = 0;
        ++crr;
        iz[bst[i].se] = crr;
        wh[crr] = bst[i].se;
    }
    dfs(1);
    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)':
regions.cpp:66: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:80: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:106: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 6 ms 5624 KB Output is correct
2 Correct 7 ms 5624 KB Output is correct
3 Correct 8 ms 5624 KB Output is correct
4 Correct 10 ms 5880 KB Output is correct
5 Correct 15 ms 5880 KB Output is correct
6 Correct 30 ms 6904 KB Output is correct
7 Correct 37 ms 6392 KB Output is correct
8 Correct 42 ms 6696 KB Output is correct
9 Correct 64 ms 7672 KB Output is correct
10 Correct 94 ms 8568 KB Output is correct
11 Correct 115 ms 7836 KB Output is correct
12 Correct 170 ms 9592 KB Output is correct
13 Correct 156 ms 8496 KB Output is correct
14 Correct 158 ms 8056 KB Output is correct
15 Correct 207 ms 10084 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 845 ms 10860 KB Output is correct
2 Correct 952 ms 10080 KB Output is correct
3 Correct 1490 ms 12624 KB Output is correct
4 Correct 690 ms 27052 KB Output is correct
5 Correct 919 ms 32228 KB Output is correct
6 Correct 1491 ms 39960 KB Output is correct
7 Correct 2391 ms 52740 KB Output is correct
8 Correct 2769 ms 56392 KB Output is correct
9 Correct 4629 ms 77100 KB Output is correct
10 Correct 5622 ms 115732 KB Output is correct
11 Correct 6561 ms 112360 KB Output is correct
12 Correct 4893 ms 82732 KB Output is correct
13 Correct 5262 ms 82600 KB Output is correct
14 Correct 6088 ms 98236 KB Output is correct
15 Correct 6114 ms 116756 KB Output is correct
16 Correct 6472 ms 119716 KB Output is correct
17 Correct 6280 ms 103388 KB Output is correct