oj.uz

Submission #649259

# Submission time Handle Problem Language Result Execution time Memory
649259 2022-10-09T22:34:36 Z vladutpiele Regions (IOI09_regions) C++17
0 / 100
 1882 ms 33204 KB 
#include <bits/stdc++.h>

using namespace std;

const int nmax = 200000;
const int block = 1000;

int n, r, q;
int region[nmax + 5], cntRegion[nmax + 5];
int bigRegion[nmax + 5], cntBigRegion, bigIdx[nmax + 5];
int smallRegion[nmax + 5], cntSmallRegion, smallIdx[nmax + 5];
int cntAbove[nmax + 5], sol[205][25005], sumePartiale[nmax + 5];
int precalc[205][25005];
int cntTimp;
pair<int, int> timp[nmax + 5];
vector<int> nodesFromRegion[nmax + 5];
vector<int> g[nmax + 5];

void dfs(int fiu, int tata)
{
    timp[fiu].first = ++cntTimp;
    /// cntAbove[i] -> numarul de noduri de regiunea i(care este o regiune de tip BIG), care sunt stramosi ai nodului curent
    if(bigIdx[region[fiu]] != 0)
    {
        cntAbove[bigIdx[region[fiu]]] ++;
    }
    for(int i = 1; i <= cntBigRegion; i ++)
    {
        sol[bigIdx[bigRegion[i]]][region[fiu]] += cntAbove[bigIdx[region[fiu]]];
    }
    for(auto it : g[fiu])
    {
        if(it == tata)
        {
            continue;
        }
        dfs(it, fiu);
    }
    if(bigIdx[region[fiu]] != 0)
    {
        cntAbove[bigIdx[region[fiu]]] ++;
    }
    timp[fiu].second = cntTimp;
}

int main()
{
    cin >> n >> r >> q;
    cin >> region[1];
    cntRegion[region[1]] ++;
    for(int i = 2; i <= n; i ++)
    {
        int p;
        cin >> p >> region[i];
        g[p].push_back(i);
        g[i].push_back(p);
        cntRegion[region[i]] ++;
        nodesFromRegion[region[i]].push_back(i);
    }
    for(int i = 1; i <= r; i ++)
    {
        if(cntRegion[i] >= block)
        {
            bigRegion[++cntBigRegion] = i;
            bigIdx[i] = cntBigRegion;
        }
        else
        {
            smallRegion[++cntSmallRegion] = i;
            smallIdx[i] = cntSmallRegion;
        }
    }

    /// in dfs calculez pentru tipurile 1 si 2, cand regiunea de sus este de tip BIG

    dfs(1, 0);

    /// imi propun sa calculez pentru tipul 3, cand regiunea de jos este de tip BIG, iar regiunea de sus este de tip SMALL

    for(int i = 1; i <= r; i ++)
    {
        if(bigIdx[i] == 0)
        {
            continue;
        }
        for(auto it : nodesFromRegion[i])
        {
            sumePartiale[timp[it].first] ++;
        }
        for(int j = 1; j <= n; j ++)
        {
            sumePartiale[j] += sumePartiale[j - 1];
        }
        for(int j = 1; j <= cntSmallRegion; j ++)
        {
            for(auto it : nodesFromRegion[smallRegion[i]])
            {
                precalc[bigIdx[i]][j] += 1LL * (sumePartiale[timp[it].second] - sumePartiale[timp[it].first] - 1);
            }
        }
        for(int j = 1; j <= n; j ++)
        {
            sumePartiale[j] = 0;
        }
    }

    while(q--)
    {
        int a, b;
        cin >> a >> b;
        if(bigIdx[a] != 0)
        {
            /// cand regiunea de sus e de tip BIG
            cout << sol[bigIdx[a]][b] << '\n';
        }
        else
        {
            if(bigIdx[b] != 0)
            {
                /// cand regiunea de jos e BIG, dar cea de sus e SMALL
                cout << precalc[bigIdx[b]][smallIdx[a]] << '\n';
            }
            else
            {
                cout << 0 << '\n';
            }
        }
    }

    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9680 KB Output isn't correct
2 Incorrect 5 ms 9680 KB Output isn't correct
3 Incorrect 7 ms 9680 KB Output isn't correct
4 Incorrect 10 ms 9680 KB Output isn't correct
5 Incorrect 13 ms 9680 KB Output isn't correct
6 Incorrect 22 ms 9808 KB Output isn't correct
7 Incorrect 35 ms 9808 KB Output isn't correct
8 Incorrect 38 ms 9808 KB Output isn't correct
9 Incorrect 67 ms 10192 KB Output isn't correct
10 Incorrect 78 ms 10192 KB Output isn't correct
11 Incorrect 83 ms 10448 KB Output isn't correct
12 Incorrect 118 ms 10960 KB Output isn't correct
13 Incorrect 103 ms 10832 KB Output isn't correct
14 Incorrect 146 ms 11144 KB Output isn't correct
15 Incorrect 225 ms 14080 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 765 ms 14500 KB Output isn't correct
2 Incorrect 685 ms 14152 KB Output isn't correct
3 Incorrect 1179 ms 16628 KB Output isn't correct
4 Incorrect 265 ms 11420 KB Output isn't correct
5 Incorrect 266 ms 13160 KB Output isn't correct
6 Incorrect 464 ms 12732 KB Output isn't correct
7 Incorrect 854 ms 13636 KB Output isn't correct
8 Incorrect 893 ms 19016 KB Output isn't correct
9 Incorrect 1409 ms 18708 KB Output isn't correct
10 Incorrect 1704 ms 24328 KB Output isn't correct
11 Incorrect 1543 ms 20548 KB Output isn't correct
12 Incorrect 747 ms 20432 KB Output isn't correct
13 Incorrect 1300 ms 21520 KB Output isn't correct
14 Incorrect 1366 ms 23396 KB Output isn't correct
15 Incorrect 1684 ms 25720 KB Output isn't correct
16 Incorrect 1882 ms 33084 KB Output isn't correct
17 Incorrect 1568 ms 33204 KB Output isn't correct