oj.uz

Submission #299151

# Submission time Handle Problem Language Result Execution time Memory
299151 2020-09-14T14:07:54 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 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 7 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 10 ms 9856 KB Output isn't correct
6 Incorrect 26 ms 9856 KB Output isn't correct
7 Incorrect 22 ms 9856 KB Output isn't correct
8 Incorrect 41 ms 9856 KB Output isn't correct
9 Incorrect 62 ms 10240 KB Output isn't correct
10 Incorrect 81 ms 10368 KB Output isn't correct
11 Incorrect 106 ms 10752 KB Output isn't correct
12 Incorrect 153 ms 11128 KB Output isn't correct
13 Incorrect 157 ms 11256 KB Output isn't correct
14 Incorrect 163 ms 11640 KB Output isn't correct
15 Incorrect 253 ms 14712 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8085 ms 14996 KB Time limit exceeded
2 Incorrect 2782 ms 15096 KB Output isn't correct
3 Execution timed out 8010 ms 17272 KB Time limit exceeded
4 Incorrect 458 ms 11804 KB Output isn't correct
5 Incorrect 853 ms 12920 KB Output isn't correct
6 Incorrect 4790 ms 17120 KB Output isn't correct
7 Incorrect 4146 ms 18904 KB Output isn't correct
8 Execution timed out 8036 ms 21752 KB Time limit exceeded
9 Incorrect 6004 ms 20216 KB Output isn't correct
10 Execution timed out 8042 ms 27816 KB Time limit exceeded
11 Execution timed out 8044 ms 21240 KB Time limit exceeded
12 Execution timed out 8042 ms 20344 KB Time limit exceeded
13 Execution timed out 8026 ms 21496 KB Time limit exceeded
14 Execution timed out 8039 ms 21880 KB Time limit exceeded
15 Execution timed out 8006 ms 25496 KB Time limit exceeded
16 Execution timed out 8071 ms 23828 KB Time limit exceeded
17 Execution timed out 8045 ms 31552 KB Time limit exceeded