oj.uz

Submission #964881

# Submission time Handle Problem Language Result Execution time Memory
964881 2024-04-17T16:54:19 Z codefox Regions (IOI09_regions) C++14
45 / 100
 3915 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<int>> backsolutions;
vector<vector<int>> frontsolutions;

int K = 140;
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);

    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);

    dpback.assign(n, vector<int>(K, 0));
    backsolutions.assign(r, vector<int>(K, -1));

    dfsback(0);
    dpback.resize(0);
    frontsolutions.assign(K, vector<int>(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 2 ms 344 KB Output is correct
5 Correct 6 ms 816 KB Output is correct
6 Correct 12 ms 1112 KB Output is correct
7 Correct 16 ms 1544 KB Output is correct
8 Correct 26 ms 1908 KB Output is correct
9 Correct 39 ms 4440 KB Output is correct
10 Correct 68 ms 7272 KB Output is correct
11 Correct 134 ms 10520 KB Output is correct
12 Correct 148 ms 14308 KB Output is correct
13 Correct 231 ms 16120 KB Output is correct
14 Correct 377 ms 20228 KB Output is correct
15 Correct 390 ms 30828 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1829 ms 51332 KB Output isn't correct
2 Incorrect 2060 ms 52400 KB Output isn't correct
3 Incorrect 3274 ms 62968 KB Output isn't correct
4 Correct 355 ms 22680 KB Output is correct
5 Correct 372 ms 30280 KB Output is correct
6 Correct 2145 ms 39224 KB Output is correct
7 Correct 2704 ms 52856 KB Output is correct
8 Correct 2426 ms 78936 KB Output is correct
9 Correct 3915 ms 110240 KB Output is correct
10 Runtime error 107 ms 131072 KB Execution killed with signal 9
11 Runtime error 101 ms 131072 KB Execution killed with signal 9
12 Runtime error 99 ms 131072 KB Execution killed with signal 9
13 Runtime error 95 ms 131072 KB Execution killed with signal 9
14 Runtime error 85 ms 131072 KB Execution killed with signal 9
15 Runtime error 83 ms 131072 KB Execution killed with signal 9
16 Runtime error 92 ms 131072 KB Execution killed with signal 9
17 Runtime error 94 ms 131072 KB Execution killed with signal 9