oj.uz

Submission #1024539

# Submission time Handle Problem Language Result Execution time Memory
1024539 2024-07-16T07:08:13 Z Ice_man Regions (IOI09_regions) C++14
100 / 100
 3532 ms 68432 KB 
/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>


#define maxn 200005
#define maxr 25005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

using namespace std;


typedef long long ll;
typedef pair <ll , ll> pll;
typedef pair <int , int> pii;
typedef long double ld;
typedef unsigned long long ull;




map <int , int> br[maxn];
int n , r , q;
vector <int> v[maxn];
int color[maxn];

vector <int> c[maxr];
map <int , int> ans[maxr];
int sz[maxn] , id[maxn];
int pre[maxn];
int timer;
vector <int> tt[maxn];


void dfs(int node , int par)
{
    id[node] = timer;
    pre[timer] = color[node];

    sz[node] = 1;
    tt[color[node]].pb(timer);

    timer++;

    for(auto& nb : v[node])
    {
        if(nb == par)
            continue;

        dfs(nb , node);
        sz[node] += sz[nb];
    }
}


bool used[maxn];
void dfs2(int node , int par , int br , int col)
{
    if(color[node] == col)
        used[node] = true;
    ans[col][color[node]] += br;

    for(auto& nb : v[node])
    {
        if(nb == par)
            continue;
        
        dfs2(nb , node , br + (col == color[node]) , col);
    }
}



int par[maxn];
void read()
{
    cin >> n >> r >> q;

    for(int i = 1; i <= n; i++)
    {
        if(i == 1)
        {
            cin >> color[i];
            c[color[i]].pb(i);
            continue;
        }

        int x;
        cin >> par[i] >> color[i];
        c[color[i]].pb(i);

        v[par[i]].pb(i);
        v[i].pb(par[i]);
    }

    int sq = 500;
    timer = 0;
    dfs(1 , 0);

    for(int i = 1; i <= r; i++)
        if(c[i].size() > 500)
            for(auto& e : c[i])
                if(used[e] == false)
                    dfs2(e , par[e] , 0 , color[e]);

    int x , y;
    while(q--)
    {
        cin >> x >> y;
        if(c[x].size() > 500)
        {
            cout << ans[x][y] << endl;
            cout.flush();
            continue;
        }

        int curr = 0;
        for(auto& e : c[x])
            curr += (upper_bound(tt[y].begin() , tt[y].end() , id[e] + sz[e] - 1) - tt[y].begin())
                        - (lower_bound(tt[y].begin() , tt[y].end() , id[e]) - tt[y].begin());

        cout << curr << endl;
        cout.flush();
    }
}










int main()
{

/**#ifdef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif*/

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ///startT = std::chrono::high_resolution_clock::now();

    read();


    return 0;
}

Compilation message

regions.cpp: In function 'void read()':
regions.cpp:106:13: warning: unused variable 'x' [-Wunused-variable]
  106 |         int x;
      |             ^
regions.cpp:114:9: warning: unused variable 'sq' [-Wunused-variable]
  114 |     int sq = 500;
      |         ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24920 KB Output is correct
2 Correct 5 ms 24920 KB Output is correct
3 Correct 6 ms 24920 KB Output is correct
4 Correct 6 ms 24920 KB Output is correct
5 Correct 8 ms 24920 KB Output is correct
6 Correct 14 ms 24920 KB Output is correct
7 Correct 20 ms 24920 KB Output is correct
8 Correct 21 ms 24920 KB Output is correct
9 Correct 32 ms 25432 KB Output is correct
10 Correct 60 ms 25432 KB Output is correct
11 Correct 84 ms 25688 KB Output is correct
12 Correct 96 ms 25944 KB Output is correct
13 Correct 149 ms 25944 KB Output is correct
14 Correct 195 ms 26456 KB Output is correct
15 Correct 185 ms 29272 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1555 ms 29528 KB Output is correct
2 Correct 1839 ms 28752 KB Output is correct
3 Correct 2379 ms 32072 KB Output is correct
4 Correct 196 ms 26456 KB Output is correct
5 Correct 267 ms 28248 KB Output is correct
6 Correct 1121 ms 27736 KB Output is correct
7 Correct 1409 ms 28504 KB Output is correct
8 Correct 994 ms 33880 KB Output is correct
9 Correct 1915 ms 33360 KB Output is correct
10 Correct 3532 ms 38836 KB Output is correct
11 Correct 3440 ms 35068 KB Output is correct
12 Correct 1206 ms 35072 KB Output is correct
13 Correct 1627 ms 36576 KB Output is correct
14 Correct 2245 ms 52492 KB Output is correct
15 Correct 2649 ms 43332 KB Output is correct
16 Correct 2446 ms 54372 KB Output is correct
17 Correct 2697 ms 68432 KB Output is correct