oj.uz

Submission #964820

# Submission time Handle Problem Language Result Execution time Memory
964820 2024-04-17T15:35:07 Z codefox Regions (IOI09_regions) C++14
19 / 100
 446 ms 131072 KB 
#include<bits/stdc++.h>

using namespace std;

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

#define pii pair<int, int>

vector<vector<int>> graph;
vector<int> region;
vector<int> rind;
vector<int> rrind;

vector<int> start;
vector<int> ende;
int c =0 ;

vector<vector<int>> dpback;

vector<vector<int>> solutions;

int K = 500;

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++)
    {
        if (rrind[j]==-1) break;
        solutions[region[i]][rrind[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++)
    {
        if (rrind[j]==-1) break;
        solutions[rrind[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);
    rrind.assign(K, -1);
    start.assign(n, 0);
    ende.assign(n, 0);
    dpback.assign(n, vector<int>(K, 0));
    solutions.assign(r, vector<int>(r, -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;
        b--;
        graph[b].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]> K) 
        {
            rrind[d] = i;
            rind[i] = d++;
        }
    }

    dfsback(0);
    dfsfront(0, vector<int>(K, 0));

    while (q--)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if (solutions[a][b]!=-1) cout << solutions[a][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 0 ms 344 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 5 ms 1624 KB Output is correct
6 Correct 16 ms 3928 KB Output is correct
7 Correct 23 ms 3672 KB Output is correct
8 Correct 23 ms 5208 KB Output is correct
9 Correct 52 ms 21440 KB Output is correct
10 Correct 84 ms 22092 KB Output is correct
11 Correct 170 ms 32964 KB Output is correct
12 Correct 211 ms 51636 KB Output is correct
13 Correct 247 ms 50320 KB Output is correct
14 Correct 446 ms 62992 KB Output is correct
15 Runtime error 87 ms 131072 KB Execution killed with signal 9

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 57 ms 131072 KB Execution killed with signal 9
2 Runtime error 57 ms 131072 KB Execution killed with signal 9
3 Runtime error 54 ms 131072 KB Execution killed with signal 9
4 Correct 429 ms 128628 KB Output is correct
5 Runtime error 51 ms 131072 KB Execution killed with signal 9
6 Runtime error 64 ms 131072 KB Execution killed with signal 9
7 Runtime error 56 ms 131072 KB Execution killed with signal 9
8 Runtime error 54 ms 131072 KB Execution killed with signal 9
9 Runtime error 52 ms 131072 KB Execution killed with signal 9
10 Runtime error 53 ms 131072 KB Execution killed with signal 9
11 Runtime error 58 ms 131072 KB Execution killed with signal 9
12 Runtime error 53 ms 131072 KB Execution killed with signal 9
13 Runtime error 52 ms 131072 KB Execution killed with signal 9
14 Runtime error 52 ms 131072 KB Execution killed with signal 9
15 Runtime error 61 ms 131072 KB Execution killed with signal 9
16 Runtime error 52 ms 131072 KB Execution killed with signal 9
17 Runtime error 52 ms 131072 KB Execution killed with signal 9