oj.uz

Submission #1024538

# Submission time Handle Problem Language Result Execution time Memory
1024538 2024-07-16T07:07:53 Z Ice_man Regions (IOI09_regions) C++14
15 / 100
 8000 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 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 4 ms 24920 KB Output is correct
3 Correct 7 ms 24952 KB Output is correct
4 Correct 6 ms 24920 KB Output is correct
5 Correct 8 ms 24904 KB Output is correct
6 Correct 32 ms 27736 KB Output is correct
7 Correct 23 ms 25688 KB Output is correct
8 Correct 31 ms 26708 KB Output is correct
9 Correct 117 ms 29772 KB Output is correct
10 Correct 133 ms 31420 KB Output is correct
11 Correct 215 ms 29008 KB Output is correct
12 Correct 576 ms 35580 KB Output is correct
13 Correct 137 ms 29776 KB Output is correct
14 Correct 263 ms 28236 KB Output is correct
15 Correct 554 ms 33360 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8021 ms 31316 KB Time limit exceeded
2 Execution timed out 8055 ms 30800 KB Time limit exceeded
3 Execution timed out 8058 ms 34900 KB Time limit exceeded
4 Runtime error 1119 ms 131072 KB Execution killed with signal 9
5 Runtime error 1685 ms 131072 KB Execution killed with signal 9
6 Runtime error 1189 ms 131072 KB Execution killed with signal 9
7 Runtime error 953 ms 131072 KB Execution killed with signal 9
8 Runtime error 1358 ms 131072 KB Execution killed with signal 9
9 Runtime error 1760 ms 131072 KB Execution killed with signal 9
10 Runtime error 1322 ms 131072 KB Execution killed with signal 9
11 Runtime error 1739 ms 131072 KB Execution killed with signal 9
12 Runtime error 2210 ms 131072 KB Execution killed with signal 9
13 Runtime error 1837 ms 131072 KB Execution killed with signal 9
14 Runtime error 1929 ms 131072 KB Execution killed with signal 9
15 Runtime error 1217 ms 131072 KB Execution killed with signal 9
16 Runtime error 1249 ms 131072 KB Execution killed with signal 9
17 Runtime error 1469 ms 131072 KB Execution killed with signal 9