oj.uz

Submission #964901

# Submission time Handle Problem Language Result Execution time Memory
964901 2024-04-17T17:08:05 Z codefox Regions (IOI09_regions) C++14
50 / 100
 3418 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>

const int K = 200;
const int N = 200000;
const int R = 25000;

vector<int> graph[N];
short region[N];
vector<int> rind;

int start[N];
int ende[N];
int c =0 ;

vector<vector<int>> dpback;

int backsolutions[R][K];
int frontsolutions[K][R];

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;

    rind.assign(r, -1);

    for (int i = 0; i < R*K; i++)
    {
        backsolutions[0][i] = 0;
        frontsolutions[0][i] = 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.clear();

    dpback.assign(n, vector<int>(K, 0));

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

    vector<pii> s;
    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
        {
            for (int ele:part[a]) 
            {
                s.push_back({start[ele], 2});
                s.push_back({ende[ele], 0});
            }
            for (int ele:part[b])
            {
                s.push_back({start[ele], 1});
            }
            sort(s.begin(), s.end());

            int open = 0;
            int sol = 0;
            for (pii ele:s)
            {
                if (ele.second == 0) open--;
                if (ele.second == 1) sol += open;
                if (ele.second == 2) open++;
            }
            cout << sol << endl;
            s.clear();
        }
    }

    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:75:29: warning: iteration 200 invokes undefined behavior [-Waggressive-loop-optimizations]
   75 |         backsolutions[0][i] = 0;
      |         ~~~~~~~~~~~~~~~~~~~~^~~
regions.cpp:73:23: note: within this loop
   73 |     for (int i = 0; i < R*K; i++)
      |                     ~~^~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 46168 KB Output is correct
2 Correct 7 ms 46204 KB Output is correct
3 Correct 8 ms 46168 KB Output is correct
4 Correct 8 ms 46168 KB Output is correct
5 Correct 10 ms 46680 KB Output is correct
6 Correct 18 ms 46940 KB Output is correct
7 Correct 24 ms 47448 KB Output is correct
8 Correct 31 ms 47960 KB Output is correct
9 Correct 45 ms 51032 KB Output is correct
10 Correct 79 ms 54836 KB Output is correct
11 Correct 141 ms 59072 KB Output is correct
12 Correct 164 ms 63840 KB Output is correct
13 Correct 224 ms 66488 KB Output is correct
14 Correct 402 ms 71884 KB Output is correct
15 Correct 400 ms 85584 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1927 ms 111912 KB Output is correct
2 Correct 1737 ms 114180 KB Output is correct
3 Correct 3418 ms 126748 KB Output is correct
4 Correct 360 ms 72280 KB Output is correct
5 Correct 426 ms 80592 KB Output is correct
6 Correct 2256 ms 91188 KB Output is correct
7 Correct 2809 ms 106876 KB Output is correct
8 Runtime error 62 ms 131072 KB Execution killed with signal 9
9 Runtime error 65 ms 131072 KB Execution killed with signal 9
10 Runtime error 78 ms 131072 KB Execution killed with signal 9
11 Runtime error 87 ms 131072 KB Execution killed with signal 9
12 Runtime error 80 ms 131072 KB Execution killed with signal 9
13 Runtime error 77 ms 131072 KB Execution killed with signal 9
14 Runtime error 83 ms 131072 KB Execution killed with signal 9
15 Runtime error 86 ms 131072 KB Execution killed with signal 9
16 Runtime error 77 ms 131072 KB Execution killed with signal 9
17 Runtime error 79 ms 131072 KB Execution killed with signal 9