답안 #649271

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
649271 2022-10-09T23:21:58 Z vladutpiele Regions (IOI09_regions) C++17
100 / 100
2960 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]] ++;
    nodesFromRegion[region[1]].push_back(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:136: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]
  136 |                 while(i < lista[a].size() && j < lista[b].size())
      |                       ~~^~~~~~~~~~~~~~~~~
regions.cpp:136: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]
  136 |                 while(i < lista[a].size() && j < lista[b].size())
      |                                              ~~^~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 11216 KB Output is correct
2 Correct 6 ms 11216 KB Output is correct
3 Correct 6 ms 11188 KB Output is correct
4 Correct 10 ms 11216 KB Output is correct
5 Correct 13 ms 11344 KB Output is correct
6 Correct 25 ms 11728 KB Output is correct
7 Correct 30 ms 11744 KB Output is correct
8 Correct 21 ms 11728 KB Output is correct
9 Correct 32 ms 12752 KB Output is correct
10 Correct 95 ms 13008 KB Output is correct
11 Correct 75 ms 13456 KB Output is correct
12 Correct 148 ms 14664 KB Output is correct
13 Correct 181 ms 14940 KB Output is correct
14 Correct 169 ms 15560 KB Output is correct
15 Correct 295 ms 20212 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 865 ms 21544 KB Output is correct
2 Correct 1127 ms 21400 KB Output is correct
3 Correct 1891 ms 25004 KB Output is correct
4 Correct 289 ms 21488 KB Output is correct
5 Correct 252 ms 25576 KB Output is correct
6 Correct 945 ms 28472 KB Output is correct
7 Correct 1375 ms 35636 KB Output is correct
8 Correct 1181 ms 43976 KB Output is correct
9 Correct 2206 ms 55072 KB Output is correct
10 Correct 2229 ms 76980 KB Output is correct
11 Correct 2960 ms 73736 KB Output is correct
12 Correct 1439 ms 58784 KB Output is correct
13 Correct 1652 ms 60600 KB Output is correct
14 Correct 2139 ms 69560 KB Output is correct
15 Correct 2409 ms 80160 KB Output is correct
16 Correct 2636 ms 90060 KB Output is correct
17 Correct 2497 ms 84384 KB Output is correct