oj.uz

Submission #1026947

# Submission time Handle Problem Language Result Execution time Memory
1026947 2024-07-18T14:35:32 Z Ice_man Regions (IOI09_regions) C++14
100 / 100
 3029 ms 69196 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;
int tout[maxn];

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];
    }
    tout[node] = timer;
}


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() , tout[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:109:13: warning: unused variable 'x' [-Wunused-variable]
  109 |         int x;
      |             ^
regions.cpp:117:9: warning: unused variable 'sq' [-Wunused-variable]
  117 |     int sq = 500;
      |         ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25688 KB Output is correct
2 Correct 4 ms 25540 KB Output is correct
3 Correct 4 ms 25688 KB Output is correct
4 Correct 5 ms 25688 KB Output is correct
5 Correct 7 ms 25660 KB Output is correct
6 Correct 10 ms 25688 KB Output is correct
7 Correct 17 ms 25688 KB Output is correct
8 Correct 20 ms 25688 KB Output is correct
9 Correct 28 ms 26200 KB Output is correct
10 Correct 57 ms 26200 KB Output is correct
11 Correct 84 ms 26456 KB Output is correct
12 Correct 105 ms 26968 KB Output is correct
13 Correct 130 ms 26712 KB Output is correct
14 Correct 210 ms 27224 KB Output is correct
15 Correct 190 ms 30040 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1534 ms 30252 KB Output is correct
2 Correct 1745 ms 29612 KB Output is correct
3 Correct 2301 ms 32948 KB Output is correct
4 Correct 196 ms 27224 KB Output is correct
5 Correct 265 ms 29016 KB Output is correct
6 Correct 1135 ms 28504 KB Output is correct
7 Correct 1416 ms 29528 KB Output is correct
8 Correct 955 ms 34640 KB Output is correct
9 Correct 1812 ms 34212 KB Output is correct
10 Correct 3029 ms 39500 KB Output is correct
11 Correct 2947 ms 35852 KB Output is correct
12 Correct 1022 ms 35856 KB Output is correct
13 Correct 1251 ms 37356 KB Output is correct
14 Correct 1881 ms 53272 KB Output is correct
15 Correct 2179 ms 44124 KB Output is correct
16 Correct 2395 ms 55152 KB Output is correct
17 Correct 2620 ms 69196 KB Output is correct