Submission #649267

# Submission time Handle Problem Language Result Execution time Memory
649267 2022-10-09T23:12:56 Z vladutpiele Regions (IOI09_regions) C++17
55 / 100
3380 ms 90060 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';
            cout << -1 << '\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';
                cout << -1 << '\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:137: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]
  137 |                 while(i < lista[a].size() && j < lista[b].size())
      |                       ~~^~~~~~~~~~~~~~~~~
regions.cpp:137: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]
  137 |                 while(i < lista[a].size() && j < lista[b].size())
      |                                              ~~^~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 6 ms 11216 KB Output is correct
2 Correct 6 ms 11240 KB Output is correct
3 Correct 8 ms 11216 KB Output is correct
4 Correct 10 ms 11216 KB Output is correct
5 Correct 15 ms 11344 KB Output is correct
6 Correct 25 ms 11728 KB Output is correct
7 Correct 38 ms 11600 KB Output is correct
8 Correct 35 ms 11728 KB Output is correct
9 Correct 64 ms 12752 KB Output is correct
10 Correct 92 ms 13008 KB Output is correct
11 Correct 114 ms 13404 KB Output is correct
12 Correct 166 ms 14624 KB Output is correct
13 Correct 188 ms 14812 KB Output is correct
14 Correct 206 ms 15444 KB Output is correct
15 Correct 249 ms 20232 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 1045 ms 21536 KB Output isn't correct
2 Incorrect 1342 ms 21348 KB Output isn't correct
3 Incorrect 1962 ms 25008 KB Output isn't correct
4 Correct 325 ms 21492 KB Output is correct
5 Correct 316 ms 25548 KB Output is correct
6 Correct 964 ms 28436 KB Output is correct
7 Correct 1115 ms 35724 KB Output is correct
8 Correct 1284 ms 44072 KB Output is correct
9 Correct 2336 ms 55084 KB Output is correct
10 Correct 2997 ms 77060 KB Output is correct
11 Correct 3011 ms 73880 KB Output is correct
12 Incorrect 1407 ms 58888 KB Output isn't correct
13 Incorrect 1831 ms 60644 KB Output isn't correct
14 Incorrect 2036 ms 69564 KB Output isn't correct
15 Incorrect 2916 ms 80152 KB Output isn't correct
16 Incorrect 3380 ms 90060 KB Output isn't correct
17 Incorrect 3246 ms 84284 KB Output isn't correct