oj.uz

Submission #1024531

# Submission time Handle Problem Language Result Execution time Memory
1024531 2024-07-16T07:01:46 Z Ice_man Regions (IOI09_regions) C++14
45 / 100
 1734 ms 131072 KB 
/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

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


#define maxn 200005
#define maxr 20005
#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];
int ans[maxr][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])
        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:101:13: warning: unused variable 'x' [-Wunused-variable]
  101 |         int x;
      |             ^
regions.cpp:109:9: warning: unused variable 'sq' [-Wunused-variable]
  109 |     int sq = 500;
      |         ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24152 KB Output is correct
2 Correct 5 ms 24152 KB Output is correct
3 Correct 4 ms 24152 KB Output is correct
4 Correct 6 ms 24152 KB Output is correct
5 Correct 8 ms 24152 KB Output is correct
6 Correct 14 ms 24152 KB Output is correct
7 Correct 18 ms 24404 KB Output is correct
8 Correct 23 ms 24408 KB Output is correct
9 Correct 23 ms 24664 KB Output is correct
10 Correct 55 ms 24664 KB Output is correct
11 Correct 87 ms 24920 KB Output is correct
12 Correct 108 ms 25432 KB Output is correct
13 Correct 126 ms 25432 KB Output is correct
14 Correct 200 ms 25756 KB Output is correct
15 Correct 186 ms 28760 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 72 ms 131072 KB Execution killed with signal 9
2 Runtime error 78 ms 131072 KB Execution killed with signal 9
3 Runtime error 77 ms 131072 KB Execution killed with signal 9
4 Correct 189 ms 25924 KB Output is correct
5 Correct 259 ms 27648 KB Output is correct
6 Correct 1074 ms 26980 KB Output is correct
7 Correct 1355 ms 27992 KB Output is correct
8 Correct 1004 ms 33112 KB Output is correct
9 Correct 1734 ms 32848 KB Output is correct
10 Runtime error 26 ms 28504 KB Execution killed with signal 11
11 Runtime error 26 ms 28504 KB Execution killed with signal 11
12 Runtime error 98 ms 131072 KB Execution killed with signal 9
13 Runtime error 99 ms 131072 KB Execution killed with signal 9
14 Runtime error 112 ms 131072 KB Execution killed with signal 9
15 Runtime error 26 ms 28504 KB Execution killed with signal 11
16 Runtime error 27 ms 28504 KB Execution killed with signal 11
17 Runtime error 95 ms 131072 KB Execution killed with signal 9