oj.uz

Submission #964832

# Submission time Handle Problem Language Result Execution time Memory
964832 2024-04-17T15:53:13 Z codefox Regions (IOI09_regions) C++14
24 / 100
 3541 ms 131072 KB 
#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")
#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 = 200;

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);
    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)/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]>K) cout << frontsolutions[rind[a]][b] << endl;
        else if (rsum[b]>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;
            int 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
14.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 8 ms 856 KB Output is correct
6 Correct 11 ms 1880 KB Output is correct
7 Correct 18 ms 1880 KB Output is correct
8 Correct 23 ms 2392 KB Output is correct
9 Correct 35 ms 6232 KB Output is correct
10 Correct 80 ms 10040 KB Output is correct
11 Correct 143 ms 14308 KB Output is correct
12 Correct 167 ms 19472 KB Output is correct
13 Correct 236 ms 22104 KB Output is correct
14 Correct 407 ms 27480 KB Output is correct
15 Incorrect 441 ms 40708 KB Output isn't correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 321 ms 131072 KB Execution killed with signal 9
2 Runtime error 2265 ms 131072 KB Execution killed with signal 9
3 Incorrect 3541 ms 84364 KB Output isn't correct
4 Correct 390 ms 33804 KB Output is correct
5 Correct 430 ms 44072 KB Output is correct
6 Incorrect 438 ms 58560 KB Output isn't correct
7 Runtime error 2483 ms 131072 KB Execution killed with signal 9
8 Runtime error 2361 ms 131072 KB Execution killed with signal 9
9 Runtime error 55 ms 131072 KB Execution killed with signal 9
10 Runtime error 52 ms 131072 KB Execution killed with signal 9
11 Runtime error 53 ms 131072 KB Execution killed with signal 9
12 Runtime error 55 ms 131072 KB Execution killed with signal 9
13 Runtime error 51 ms 131072 KB Execution killed with signal 9
14 Runtime error 52 ms 131072 KB Execution killed with signal 9
15 Runtime error 52 ms 131072 KB Execution killed with signal 9
16 Runtime error 55 ms 131072 KB Execution killed with signal 9
17 Runtime error 51 ms 131072 KB Execution killed with signal 9