oj.uz

Submission #964861

# Submission time Handle Problem Language Result Execution time Memory
964861 2024-04-17T16:44:25 Z codefox Regions (IOI09_regions) C++14
45 / 100
 4260 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 = 150;
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 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 4 ms 344 KB Output is correct
5 Correct 5 ms 856 KB Output is correct
6 Correct 9 ms 1488 KB Output is correct
7 Correct 23 ms 1624 KB Output is correct
8 Correct 23 ms 1880 KB Output is correct
9 Correct 33 ms 4952 KB Output is correct
10 Correct 78 ms 7848 KB Output is correct
11 Correct 151 ms 11164 KB Output is correct
12 Correct 170 ms 15232 KB Output is correct
13 Correct 241 ms 17068 KB Output is correct
14 Correct 427 ms 21288 KB Output is correct
15 Correct 407 ms 32492 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1963 ms 53592 KB Output isn't correct
2 Incorrect 1890 ms 55040 KB Output isn't correct
3 Incorrect 3526 ms 65956 KB Output isn't correct
4 Correct 426 ms 26132 KB Output is correct
5 Correct 417 ms 34572 KB Output is correct
6 Correct 2315 ms 45248 KB Output is correct
7 Correct 2938 ms 61316 KB Output is correct
8 Correct 2664 ms 88324 KB Output is correct
9 Correct 4260 ms 124212 KB Output is correct
10 Runtime error 56 ms 131072 KB Execution killed with signal 9
11 Runtime error 54 ms 131072 KB Execution killed with signal 9
12 Runtime error 57 ms 131072 KB Execution killed with signal 9
13 Runtime error 54 ms 131072 KB Execution killed with signal 9
14 Runtime error 56 ms 131072 KB Execution killed with signal 9
15 Runtime error 57 ms 131072 KB Execution killed with signal 9
16 Runtime error 56 ms 131072 KB Execution killed with signal 9
17 Runtime error 60 ms 131072 KB Execution killed with signal 9