oj.uz

Submission #175989

# Submission time Handle Problem Language Result Execution time Memory
175989 2020-01-07T13:43:14 Z stefdasca Regions (IOI09_regions) C++14
100 / 100
 5336 ms 71044 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, 500); ++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 - 499); --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 7 ms 5752 KB Output is correct
2 Correct 6 ms 5624 KB Output is correct
3 Correct 7 ms 5624 KB Output is correct
4 Correct 11 ms 5880 KB Output is correct
5 Correct 11 ms 5880 KB Output is correct
6 Correct 24 ms 7032 KB Output is correct
7 Correct 35 ms 6520 KB Output is correct
8 Correct 40 ms 6776 KB Output is correct
9 Correct 61 ms 7672 KB Output is correct
10 Correct 101 ms 8540 KB Output is correct
11 Correct 95 ms 7928 KB Output is correct
12 Correct 156 ms 9464 KB Output is correct
13 Correct 162 ms 8568 KB Output is correct
14 Correct 163 ms 8312 KB Output is correct
15 Correct 221 ms 10104 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 815 ms 10860 KB Output is correct
2 Correct 958 ms 9976 KB Output is correct
3 Correct 1390 ms 12620 KB Output is correct
4 Correct 390 ms 17144 KB Output is correct
5 Correct 541 ms 20248 KB Output is correct
6 Correct 913 ms 24172 KB Output is correct
7 Correct 1382 ms 31128 KB Output is correct
8 Correct 1648 ms 34592 KB Output is correct
9 Correct 3228 ms 45780 KB Output is correct
10 Correct 3750 ms 66820 KB Output is correct
11 Correct 5336 ms 63520 KB Output is correct
12 Correct 2653 ms 49612 KB Output is correct
13 Correct 3139 ms 49436 KB Output is correct
14 Correct 3095 ms 57336 KB Output is correct
15 Correct 4476 ms 67796 KB Output is correct
16 Correct 3682 ms 71044 KB Output is correct
17 Correct 3902 ms 62236 KB Output is correct