oj.uz

Submission #964842

# Submission time Handle Problem Language Result Execution time Memory
964842 2024-04-17T16:08:06 Z codefox Regions (IOI09_regions) C++14
50 / 100
 8000 ms 131072 KB 
#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Os")
#pragma GCC target("avx,avx2,fma")

#define ll long long
#define pii pair<int, short>

vector<vector<int>> graph;
vector<short> region;
vector<int> rind;

vector<int> start;
vector<int> ende;
int c =0 ;

vector<vector<int>> dpback;

vector<vector<ll>> backsolutions;
vector<vector<ll>> frontsolutions;

int K = 100;
int N = 201000;

void dfsback(int i)
{
    start[i] = c++;
    for (int ele:graph[i])
    {
        dfsback(ele);
        for (int j = 0; j < K; j++)
        {
            dpback[i][j] += dpback[ele][j];
        }
    }
    for (int j = 0; j < K; j++)
    {
        backsolutions[region[i]][j] = dpback[i][j];
    }
    if (rind[region[i]]!= -1) dpback[i][rind[region[i]]]++;
    ende[i] = c;
}

void dfsfront(int i, vector<int> dpfront)
{
    for (int j = 0; j < K; j++)
    {
        frontsolutions[j][region[i]] = dpfront[j];
    }
    if (rind[region[i]]!=-1) dpfront[rind[region[i]]]++;
    for (int ele:graph[i])
    {
        dfsfront(ele, dpfront);
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, r, q;
    cin >> n >> r >> q;

    graph.assign(n, vector<int>());
    region.assign(n, 0);
    rind.assign(r, -1);
    start.assign(n, 0);
    ende.assign(n, 0);
    dpback.assign(n, vector<int>(K, 0));
    backsolutions.assign(r, vector<ll>(K, -1));


    vector<vector<int>> part(r);

    cin >> region[0];
    region[0]--;
    part[region[0]].push_back(0);
    for (int i = 1; i < n; i++)
    {
        int b;
        cin >> b;
        graph[b-1].push_back(i);
        cin >> region[i];
        region[i]--;
        part[region[i]].push_back(i);
    }

    vector<int> rsum(r, 0);
    int d =0;
    for (int i = 0; i < n; i++) rsum[region[i]]++;
    for (int i = 0; i < r; i++)
    {
        if (rsum[i]> N/K) 
        {
            rind[i] = d++;
        }
    }

    rsum.resize(0);
    dfsback(0);
    dpback.resize(0);
    frontsolutions.assign(K, vector<ll>(r, -1));
    dfsfront(0, vector<int>(K, 0));

    while (q--)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if (rsum[a]>N/K) cout << frontsolutions[rind[a]][b] << endl;
        else if (rsum[b]>N/K) cout << backsolutions[a][rind[b]] << endl;
        else
        {
            vector<pii> s;
            for (int ele:part[a]) 
            {
                s.push_back({start[ele], 0});
                s.push_back({ende[ele], 1});
            }
            for (int ele:part[b])
            {
                s.push_back({start[ele], 2});
            }
            sort(s.begin(), s.end());

            int open = 0;
            ll sol = 0;
            for (pii ele:s)
            {
                if (ele.second == 0) open++;
                if (ele.second == 1) open--;
                if (ele.second == 2) sol += open;
            }
            cout << sol << endl;
        }
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 4 ms 600 KB Output is correct
6 Correct 11 ms 1112 KB Output is correct
7 Correct 21 ms 1112 KB Output is correct
8 Correct 23 ms 1628 KB Output is correct
9 Correct 36 ms 3928 KB Output is correct
10 Correct 85 ms 5800 KB Output is correct
11 Correct 148 ms 8256 KB Output is correct
12 Correct 151 ms 11352 KB Output is correct
13 Correct 244 ms 12444 KB Output is correct
14 Correct 428 ms 15568 KB Output is correct
15 Correct 433 ms 24676 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2013 ms 39420 KB Output isn't correct
2 Incorrect 2189 ms 39924 KB Output isn't correct
3 Incorrect 3708 ms 48948 KB Output isn't correct
4 Correct 390 ms 18932 KB Output is correct
5 Correct 392 ms 25664 KB Output is correct
6 Correct 2342 ms 32728 KB Output is correct
7 Correct 2947 ms 44252 KB Output is correct
8 Correct 2657 ms 65624 KB Output is correct
9 Correct 4302 ms 90256 KB Output is correct
10 Execution timed out 8015 ms 115676 KB Time limit exceeded
11 Correct 7243 ms 120012 KB Output is correct
12 Incorrect 1885 ms 109604 KB Output isn't correct
13 Incorrect 2648 ms 110524 KB Output isn't correct
14 Incorrect 5010 ms 117548 KB Output isn't correct
15 Incorrect 4799 ms 128868 KB Output isn't correct
16 Runtime error 284 ms 131072 KB Execution killed with signal 9
17 Runtime error 331 ms 131072 KB Execution killed with signal 9