oj.uz

Submission #175984

# Submission time Handle Problem Language Result Execution time Memory
175984 2020-01-07T13:21:46 Z stefdasca Regions (IOI09_regions) C++14
75 / 100
 8000 ms 119776 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 - 999); --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 5624 KB Output is correct
2 Correct 8 ms 5624 KB Output is correct
3 Correct 11 ms 5752 KB Output is correct
4 Correct 12 ms 5752 KB Output is correct
5 Correct 13 ms 5880 KB Output is correct
6 Correct 18 ms 6904 KB Output is correct
7 Correct 38 ms 6520 KB Output is correct
8 Correct 48 ms 6776 KB Output is correct
9 Correct 89 ms 7672 KB Output is correct
10 Correct 192 ms 8596 KB Output is correct
11 Correct 260 ms 7960 KB Output is correct
12 Correct 389 ms 9528 KB Output is correct
13 Correct 462 ms 8488 KB Output is correct
14 Correct 331 ms 8160 KB Output is correct
15 Correct 288 ms 10084 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1232 ms 10872 KB Output is correct
2 Correct 1407 ms 10184 KB Output is correct
3 Correct 1567 ms 12664 KB Output is correct
4 Correct 1206 ms 27112 KB Output is correct
5 Correct 920 ms 32120 KB Output is correct
6 Correct 2256 ms 39984 KB Output is correct
7 Correct 3245 ms 52856 KB Output is correct
8 Correct 2427 ms 56284 KB Output is correct
9 Execution timed out 8048 ms 77116 KB Time limit exceeded
10 Correct 4794 ms 115676 KB Output is correct
11 Execution timed out 8016 ms 75788 KB Time limit exceeded
12 Execution timed out 8020 ms 32848 KB Time limit exceeded
13 Execution timed out 8045 ms 74584 KB Time limit exceeded
14 Execution timed out 8055 ms 40868 KB Time limit exceeded
15 Correct 6982 ms 116928 KB Output is correct
16 Correct 4495 ms 119776 KB Output is correct
17 Correct 4755 ms 103488 KB Output is correct