oj.uz

Submission #964889

# Submission time Handle Problem Language Result Execution time Memory
964889 2024-04-17T17:01:12 Z codefox Regions (IOI09_regions) C++14
40 / 100
 3618 ms 131072 KB 
#include<bits/stdc++.h>

using namespace std;

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

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

    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]*K > N) 
        {
            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 (rind[a]!=-1) cout << frontsolutions[rind[a]][b] << endl;
        else if (rind[b]!=-1) 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
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 496 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 6 ms 932 KB Output is correct
6 Correct 12 ms 1624 KB Output is correct
7 Correct 22 ms 1880 KB Output is correct
8 Correct 29 ms 2392 KB Output is correct
9 Correct 45 ms 5876 KB Output is correct
10 Correct 83 ms 9696 KB Output is correct
11 Correct 148 ms 14076 KB Output is correct
12 Correct 176 ms 19088 KB Output is correct
13 Correct 243 ms 21796 KB Output is correct
14 Correct 434 ms 27292 KB Output is correct
15 Correct 451 ms 40312 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2028 ms 68764 KB Output isn't correct
2 Incorrect 1827 ms 71212 KB Output isn't correct
3 Incorrect 3618 ms 84144 KB Output isn't correct
4 Correct 405 ms 30644 KB Output is correct
5 Correct 440 ms 40120 KB Output is correct
6 Correct 2434 ms 53060 KB Output is correct
7 Correct 2969 ms 71620 KB Output is correct
8 Correct 2755 ms 104732 KB Output is correct
9 Runtime error 167 ms 131072 KB Execution killed with signal 9
10 Runtime error 130 ms 131072 KB Execution killed with signal 9
11 Runtime error 150 ms 131072 KB Execution killed with signal 9
12 Runtime error 163 ms 131072 KB Execution killed with signal 9
13 Runtime error 152 ms 131072 KB Execution killed with signal 9
14 Runtime error 155 ms 131072 KB Execution killed with signal 9
15 Runtime error 171 ms 131072 KB Execution killed with signal 9
16 Runtime error 146 ms 131072 KB Execution killed with signal 9
17 Runtime error 156 ms 131072 KB Execution killed with signal 9