oj.uz

Submission #299154

# Submission time Handle Problem Language Result Execution time Memory
299154 2020-09-14T14:09:00 Z mat_v Regions (IOI09_regions) C++14
1 / 100
 8000 ms 31552 KB 
#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define pb push_back
#define maxn 200005
#define pair<int,int> pii
#define xx first
#define yy second



using namespace std;
typedef long long ll;

int n,r,q;
int dlt;
int niz[maxn];
bool veci[maxn];
int cale[maxn];
vector<int> graf[maxn];
vector<int> boja[maxn];

int disc[maxn];
int out[maxn];
int gde[maxn];
int slika[505];


int kolko[505][25005][2];


int tajm = 1;
void dfs(int x){
    disc[x] = tajm;
    for(auto c:graf[x]){
        if(c == cale[x])continue;
        tajm++;
        dfs(c);
    }
    out[x] = tajm;
}

void color(int x, int last, int root, int idx){
    kolko[root][niz[x]][idx]++;
    for(auto c:graf[x]){
        if(c == last)continue;
        color(c,x,root,idx);
    }
}

void color2(int x, int root, int idx){
    if(x == 0)return;
    kolko[root][niz[x]][idx]++;
    color2(cale[x], root, idx);
}

bool cmp(int x, int y){
    if(out[x] == out[y])return disc[x] < disc[y];
    return out[x] < out[y];
}

int trg;

int subtr[maxn];
bool mark[maxn];

int val[maxn];
int resi(int x){
    if(mark[x])return subtr[x];
    if(x == 1)return niz[x] == trg;
    mark[x] = 1;
    return subtr[x] = resi(cale[x]) + (niz[x] == trg);
}

int main()
{
    ios_base::sync_with_stdio(false);

    cin >> n >> r >> q;
    while(dlt * dlt < n)dlt++;
    ff(i,1,n){
        if(i == 1){
            cin >> niz[i];
            boja[niz[i]].pb(i);
            continue;
        }
        cin >> cale[i];
        cin >> niz[i];
        graf[i].pb(cale[i]);
        boja[niz[i]].pb(i);
        graf[cale[i]].pb(i);
    }
    int br = 1;
    ff(i,1,r){
        int sta = boja[i].size();
        if(sta >= dlt)veci[i] = 1;
        if(veci[i]){
            slika[br] = i;
            gde[i] = br;
            //cout << i << ": \n";
            for(auto c:boja[i]){
                //cout << c << " ";
                color(c,cale[c],br,0);
                color2(cale[c],br,1);
                kolko[br][i][0]--;
            }
            //cout << kolko[br][1][0] << "\n";
            //cout << "\n";
            br++;
            continue;
        }
        sort(boja[i].begin(), boja[i].end(), cmp);
        ff(i,1,n)subtr[i] = 0;
        ff(i,1,n)mark[i] = 0;
        trg = i;
        for(auto c:boja[i]){
            val[c] = resi(c);
        }


    }
    dfs(1);
    while(q--){
        int r1,r2;
        cin >> r1 >> r2;
        if(veci[r1] || veci[r2]){
            //cout << "AAAA\n";
            if(veci[r1]){
                cout << kolko[gde[r1]][r2][0] << endl;
            }
            else{
                cout << kolko[gde[r2]][r1][1] << endl;
            }
        }
        else{
            //cout << "BBBB\n";
            int p1 = 0;
            int p2 = 0;
            int ans = 0;
            while(p1 < boja[r1].size() && p2 < boja[r2].size()){
                int prvi = boja[r1][p1];
                int drugi = boja[r2][p2];
                if(out[prvi] < out[drugi]){
                    p1++;
                    continue;
                }
                else{
                    ans += val[prvi];
                    p2++;
                }
            }
            cout << ans << endl;
        }
    }
    return 0;
}

Compilation message

regions.cpp:5:9: warning: ISO C++11 requires whitespace after the macro name
    5 | #define pair<int,int> pii
      |         ^~~~
regions.cpp: In function 'int main()':
regions.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
regions.cpp:80:5: note: in expansion of macro 'ff'
   80 |     ff(i,1,n){
      |     ^~
regions.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
regions.cpp:93:5: note: in expansion of macro 'ff'
   93 |     ff(i,1,r){
      |     ^~
regions.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
regions.cpp:112:9: note: in expansion of macro 'ff'
  112 |         ff(i,1,n)subtr[i] = 0;
      |         ^~
regions.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
regions.cpp:113:9: note: in expansion of macro 'ff'
  113 |         ff(i,1,n)mark[i] = 0;
      |         ^~
regions.cpp:139:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |             while(p1 < boja[r1].size() && p2 < boja[r2].size()){
      |                   ~~~^~~~~~~~~~~~~~~~~
regions.cpp:139:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |             while(p1 < boja[r1].size() && p2 < boja[r2].size()){
      |                                           ~~~^~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Incorrect 7 ms 9728 KB Output isn't correct
3 Incorrect 9 ms 9728 KB Output isn't correct
4 Incorrect 12 ms 9728 KB Output isn't correct
5 Incorrect 13 ms 9856 KB Output isn't correct
6 Incorrect 27 ms 9856 KB Output isn't correct
7 Incorrect 35 ms 9856 KB Output isn't correct
8 Incorrect 39 ms 9856 KB Output isn't correct
9 Incorrect 61 ms 10232 KB Output isn't correct
10 Incorrect 85 ms 10368 KB Output isn't correct
11 Incorrect 111 ms 10752 KB Output isn't correct
12 Incorrect 165 ms 11128 KB Output isn't correct
13 Incorrect 160 ms 11264 KB Output isn't correct
14 Incorrect 171 ms 11640 KB Output isn't correct
15 Incorrect 340 ms 14712 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8102 ms 14968 KB Time limit exceeded
2 Incorrect 3277 ms 15224 KB Output isn't correct
3 Execution timed out 8048 ms 16780 KB Time limit exceeded
4 Incorrect 482 ms 11900 KB Output isn't correct
5 Incorrect 944 ms 12884 KB Output isn't correct
6 Incorrect 7201 ms 17076 KB Output isn't correct
7 Incorrect 5791 ms 19020 KB Output isn't correct
8 Execution timed out 8012 ms 21216 KB Time limit exceeded
9 Incorrect 6625 ms 19968 KB Output isn't correct
10 Execution timed out 8074 ms 27536 KB Time limit exceeded
11 Execution timed out 8073 ms 21240 KB Time limit exceeded
12 Execution timed out 8042 ms 20676 KB Time limit exceeded
13 Execution timed out 8055 ms 21504 KB Time limit exceeded
14 Execution timed out 8048 ms 21740 KB Time limit exceeded
15 Execution timed out 8077 ms 22008 KB Time limit exceeded
16 Execution timed out 8092 ms 23888 KB Time limit exceeded
17 Execution timed out 8053 ms 31552 KB Time limit exceeded