oj.uz

Submission #175983

# Submission time Handle Problem Language Result Execution time Memory
175983 2020-01-07T13:19:10 Z stefdasca Regions (IOI09_regions) C++14
30 / 100
 8000 ms 131072 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 >= min(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 10 ms 9964 KB Output is correct
2 Correct 10 ms 9848 KB Output is correct
3 Correct 13 ms 9976 KB Output is correct
4 Correct 16 ms 9976 KB Output is correct
5 Correct 26 ms 9976 KB Output is correct
6 Correct 38 ms 10872 KB Output is correct
7 Correct 42 ms 10488 KB Output is correct
8 Correct 74 ms 10748 KB Output is correct
9 Correct 92 ms 11384 KB Output is correct
10 Correct 352 ms 12132 KB Output is correct
11 Correct 523 ms 11680 KB Output is correct
12 Correct 646 ms 12920 KB Output is correct
13 Correct 1062 ms 12256 KB Output is correct
14 Correct 1278 ms 12196 KB Output is correct
15 Correct 625 ms 13996 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2701 ms 14868 KB Output is correct
2 Correct 3286 ms 14196 KB Output is correct
3 Correct 2762 ms 16592 KB Output is correct
4 Runtime error 993 ms 53468 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 611 ms 63352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 1752 ms 78872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 2521 ms 103924 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 1642 ms 109840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 7097 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 3315 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Execution timed out 8041 ms 74660 KB Time limit exceeded
12 Execution timed out 8034 ms 31076 KB Time limit exceeded
13 Execution timed out 8103 ms 63248 KB Time limit exceeded
14 Execution timed out 8070 ms 38920 KB Time limit exceeded
15 Runtime error 5509 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 2742 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 2925 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)