oj.uz

Submission #1024503

# Submission time Handle Problem Language Result Execution time Memory
1024503 2024-07-16T06:20:17 Z Ice_man Regions (IOI09_regions) C++14
25 / 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 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];

void dfs(int node , int par , int col)
{
    ans[col][color[node]]++;
    for(auto& nb : v[node])
    {
        if(nb == par)
            continue;
        dfs(nb , 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]);
    }

    for(int i = 1; i <= n; i++)
        dfs(i , par[i] , color[i]);

    while(q--)
    {
        int x , y;
        cin >> x >> y;
        cout << ans[x][y] << 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:75:13: warning: unused variable 'x' [-Wunused-variable]
   75 |         int x;
      |             ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19032 KB Output is correct
2 Correct 2 ms 19032 KB Output is correct
3 Correct 3 ms 21080 KB Output is correct
4 Correct 5 ms 21168 KB Output is correct
5 Correct 7 ms 23128 KB Output is correct
6 Correct 15 ms 37496 KB Output is correct
7 Correct 16 ms 31320 KB Output is correct
8 Correct 18 ms 33368 KB Output is correct
9 Correct 111 ms 42072 KB Output is correct
10 Correct 56 ms 52312 KB Output is correct
11 Correct 127 ms 40280 KB Output is correct
12 Correct 596 ms 54872 KB Output is correct
13 Correct 105 ms 46680 KB Output is correct
14 Correct 191 ms 34744 KB Output is correct
15 Correct 5679 ms 41112 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 7793 ms 37068 KB Output is correct
2 Correct 2104 ms 38992 KB Output is correct
3 Execution timed out 8074 ms 44628 KB Time limit exceeded
4 Runtime error 78 ms 131072 KB Execution killed with signal 9
5 Runtime error 42 ms 131072 KB Execution killed with signal 9
6 Runtime error 88 ms 131072 KB Execution killed with signal 9
7 Runtime error 92 ms 131072 KB Execution killed with signal 9
8 Runtime error 67 ms 131072 KB Execution killed with signal 9
9 Runtime error 160 ms 131072 KB Execution killed with signal 9
10 Runtime error 22 ms 16984 KB Execution killed with signal 11
11 Runtime error 21 ms 16984 KB Execution killed with signal 11
12 Runtime error 431 ms 131072 KB Execution killed with signal 9
13 Runtime error 288 ms 131072 KB Execution killed with signal 9
14 Runtime error 291 ms 131072 KB Execution killed with signal 9
15 Runtime error 21 ms 16984 KB Execution killed with signal 11
16 Runtime error 22 ms 16984 KB Execution killed with signal 11
17 Runtime error 149 ms 131072 KB Execution killed with signal 9