Submission #299197

#	Time	Username	Problem	Language	Result	Execution time	Memory
299197		mat_v	Regions (IOI09_regions)	C++14	4 / 100	8096 ms	33528 KiB

regions

#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];


struct kurac{
    int l;
    int op;
    int idx;
    int pre;
};

bool cmpkurac(kurac a, kurac b){
    if(a.l != b.l)return a.l < b.l;
    if(a.l == b.l){
        if(a.op == 0)return 1;
        if(b.op == 0)return 0;
        return a.pre > b.pre;
    }
}

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);
    }
    dfs(1);
    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);
        vector<kurac> all;
        for(auto c:boja[i]){
            //cout << c << " " << disc[c] << " " << out[c] << "\n";
            all.pb({disc[c], 0, c, 0});
            all.pb({out[c], 1, c, disc[c]});
        }
        sort(all.begin(), all.end(), cmpkurac);
        int sad = 0;
        for(auto c:all){
            if(c.op == 0)sad++;
            else{
                val[c.idx] = sad;
                sad--;
            }
        }
        //return 0;


    }

    while(q--){
        int r1,r2;
        cin >> r1 >> r2;
        cout << endl;
        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];
                //cout << prvi << " " << drugi << "\n";
                //cout << disc[prvi] << " " << out[prvi] << " " << out[drugi] << "\n";
                if(out[drugi] > out[prvi]){
                    p1++;
                }
                else{
                    if(out[drugi] <= out[prvi]){
                        if(disc[drugi] > disc[prvi]){
                            ans += val[prvi];
                            p2++;
                        }
                        else{
                            p1++;
                        }
                    }
                }
            }
            cout << ans << endl;
        }
    }
    return 0;
}

Compilation message (stderr)

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:91:5: note: in expansion of macro 'ff'
   91 |     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:105:5: note: in expansion of macro 'ff'
  105 |     ff(i,1,r){
      |     ^~
regions.cpp:162:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |             while(p1 < boja[r1].size() && p2 < boja[r2].size()){
      |                   ~~~^~~~~~~~~~~~~~~~~
regions.cpp:162:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |             while(p1 < boja[r1].size() && p2 < boja[r2].size()){
      |                                           ~~~^~~~~~~~~~~~~~~~~
regions.cpp: In function 'bool cmpkurac(kurac, kurac)':
regions.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
   83 | }
      | ^

• Subtask 1: 4 / 15
• Subtask 2: 0 / 85