oj.uz

Submission #649266

# Submission time Handle Problem Language Result Execution time Memory
649266 2022-10-09T23:08:58 Z vladutpiele Regions (IOI09_regions) C++17
0 / 100
 605 ms 90104 KB 
#include <bits/stdc++.h>

#define int long long

using namespace std;

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

long long 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];
long long cntAbove[nmax + 5], sol[205][25005], sumePartiale[nmax + 5];
long long precalc[205][25005];
int cntTimp, newtime;
int stiva[nmax + 5];
vector<pair<int, int>> lista[25005];
pair<int, int> timp[nmax + 5];
vector<int> nodesFromRegion[nmax + 5];
vector<int> g[nmax + 5];

void dfs(int fiu, int tata)
{
    newtime++;
    lista[region[fiu]].push_back(make_pair(fiu, newtime));
    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 <= 200; i ++)
    {
        sol[i][region[fiu]] += 1LL * cntAbove[i];
    }
    for(auto it : g[fiu])
    {
        if(it == tata)
        {
            continue;
        }
        dfs(it, fiu);
    }
    if(bigIdx[region[fiu]] != 0)
    {
        cntAbove[bigIdx[region[fiu]]] ++;
    }
    newtime++;
    lista[region[fiu]].push_back(make_pair(fiu, newtime));
    timp[fiu].second = cntTimp;
}

signed 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(long long i = 1; i <= r; i ++)
    {
        if(bigIdx[i] == 0)
        {
            continue;
        }
        for(auto it : nodesFromRegion[i])
        {
            sumePartiale[timp[it].first] ++;
        }
        for(long long j = 1; j <= n; j ++)
        {
            sumePartiale[j] += 1LL * sumePartiale[j - 1];
        }
        for(long long j = 1; j <= cntSmallRegion; j ++)
        {
            for(auto it : nodesFromRegion[smallRegion[j]])
            {
                precalc[bigIdx[i]][j] += 1LL * (sumePartiale[timp[it].second] - sumePartiale[timp[it].first - 1]);
            }
        }
        for(long long j = 1; j <= n; j ++)
        {
            sumePartiale[j] = 0;
        }
    }

    while(q--)
    {
        long long 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
            {
                long long i = 0, j = 0, vf = 0;
                long long deschise = 0, answer = 0;
                while(i < lista[a].size() && j < lista[b].size())
                {
                    pair<int, int> frst = lista[a][i];
                    pair<int, int> scnd = lista[b][j];
                    if(frst.second < scnd.second)
                    {
                        if(vf && frst.first == stiva[vf])
                        {
                            vf--;
                            deschise--;
                        }
                        else
                        {
                            stiva[++vf] = frst.first;
                            deschise++;
                        }
                        i++;
                    }
                    else
                    {
                        if(vf && scnd.first == stiva[vf])
                        {
                            vf--;
                        }
                        else
                        {
                            answer += 1LL * deschise;
                            stiva[++vf] = scnd.first;
                        }
                        j++;
                    }
                }
                ///cout << answer << '\n';
            }
        }
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:135:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |                 while(i < lista[a].size() && j < lista[b].size())
      |                       ~~^~~~~~~~~~~~~~~~~
regions.cpp:135:48: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |                 while(i < lista[a].size() && j < lista[b].size())
      |                                              ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8 ms 11216 KB Time limit exceeded (wall clock)
2 Execution timed out 6 ms 11216 KB Time limit exceeded (wall clock)
3 Execution timed out 6 ms 11236 KB Time limit exceeded (wall clock)
4 Execution timed out 5 ms 11216 KB Time limit exceeded (wall clock)
5 Execution timed out 5 ms 11344 KB Time limit exceeded (wall clock)
6 Execution timed out 6 ms 11728 KB Time limit exceeded (wall clock)
7 Execution timed out 6 ms 11600 KB Time limit exceeded (wall clock)
8 Execution timed out 8 ms 11728 KB Time limit exceeded (wall clock)
9 Execution timed out 10 ms 12752 KB Time limit exceeded (wall clock)
10 Execution timed out 15 ms 13008 KB Time limit exceeded (wall clock)
11 Execution timed out 18 ms 13368 KB Time limit exceeded (wall clock)
12 Execution timed out 27 ms 14664 KB Time limit exceeded (wall clock)
13 Execution timed out 29 ms 14888 KB Time limit exceeded (wall clock)
14 Execution timed out 29 ms 15384 KB Time limit exceeded (wall clock)
15 Execution timed out 43 ms 20152 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 80 ms 21500 KB Time limit exceeded (wall clock)
2 Execution timed out 84 ms 21224 KB Time limit exceeded (wall clock)
3 Execution timed out 107 ms 25124 KB Time limit exceeded (wall clock)
4 Execution timed out 66 ms 21364 KB Time limit exceeded (wall clock)
5 Execution timed out 86 ms 25508 KB Time limit exceeded (wall clock)
6 Execution timed out 129 ms 28448 KB Time limit exceeded (wall clock)
7 Execution timed out 249 ms 35572 KB Time limit exceeded (wall clock)
8 Execution timed out 264 ms 44044 KB Time limit exceeded (wall clock)
9 Execution timed out 439 ms 55052 KB Time limit exceeded (wall clock)
10 Execution timed out 474 ms 77000 KB Time limit exceeded (wall clock)
11 Execution timed out 605 ms 73620 KB Time limit exceeded (wall clock)
12 Execution timed out 557 ms 58808 KB Time limit exceeded (wall clock)
13 Execution timed out 519 ms 60536 KB Time limit exceeded (wall clock)
14 Execution timed out 586 ms 69452 KB Time limit exceeded (wall clock)
15 Execution timed out 557 ms 80212 KB Time limit exceeded (wall clock)
16 Execution timed out 522 ms 90104 KB Time limit exceeded (wall clock)
17 Execution timed out 554 ms 84252 KB Time limit exceeded (wall clock)