oj.uz

Submission #964840

# Submission time Handle Problem Language Result Execution time Memory
964840 2024-04-17T16:06:44 Z codefox Regions (IOI09_regions) C++14
40 / 100
 3576 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 = 200;
int N = 200000;

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 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 3 ms 600 KB Output is correct
5 Correct 5 ms 856 KB Output is correct
6 Correct 9 ms 1880 KB Output is correct
7 Correct 20 ms 1880 KB Output is correct
8 Correct 24 ms 2392 KB Output is correct
9 Correct 40 ms 6228 KB Output is correct
10 Correct 83 ms 10040 KB Output is correct
11 Correct 142 ms 14312 KB Output is correct
12 Correct 161 ms 19468 KB Output is correct
13 Correct 249 ms 22096 KB Output is correct
14 Correct 427 ms 27472 KB Output is correct
15 Correct 454 ms 40712 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2058 ms 68936 KB Output isn't correct
2 Incorrect 1854 ms 71408 KB Output isn't correct
3 Incorrect 3576 ms 84372 KB Output isn't correct
4 Correct 389 ms 33796 KB Output is correct
5 Correct 429 ms 44060 KB Output is correct
6 Correct 2394 ms 58564 KB Output is correct
7 Correct 3008 ms 79480 KB Output is correct
8 Correct 2805 ms 112584 KB Output is correct
9 Runtime error 51 ms 131072 KB Execution killed with signal 9
10 Runtime error 51 ms 131072 KB Execution killed with signal 9
11 Runtime error 63 ms 131072 KB Execution killed with signal 9
12 Runtime error 52 ms 131072 KB Execution killed with signal 9
13 Runtime error 56 ms 131072 KB Execution killed with signal 9
14 Runtime error 54 ms 131072 KB Execution killed with signal 9
15 Runtime error 52 ms 131072 KB Execution killed with signal 9
16 Runtime error 63 ms 131072 KB Execution killed with signal 9
17 Runtime error 54 ms 131072 KB Execution killed with signal 9