Submission #299108

#	Time	Username	Problem	Language	Result	Execution time	Memory
299108		mat_v	Regions (IOI09_regions)	C++14	12 / 100	8099 ms	103156 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

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);
    }
}

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


int subtr[maxn];


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 >= 0)veci[i] = 1;
        if(veci[i]){
            slika[br] = i;
            gde[i] = br;
            for(auto c:boja[i]){
                color(cale[c],c,br,1);
                color(c,cale[c],br,0);
                kolko[br][i][0]--;
            }
            br++;
        }
        else{

        }

    }
    dfs(1);
    while(q--){
        int r1,r2;
        cin >> r1 >> r2;
        if(veci[r1] || veci[r2]){
            if(veci[r1]){
                cout << kolko[gde[r1]][r2][0] << endl;
            }
            else{
                cout << kolko[gde[r2]][r1][1] << endl;
            }
        }
        else{
            int p1 = 0;
            int p2 = 0;
        }
    }
    return 0;
}

Compilation message (stderr)

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:59:5: note: in expansion of macro 'ff'
   59 |     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:72:5: note: in expansion of macro 'ff'
   72 |     ff(i,1,r){
      |     ^~
regions.cpp:103:17: warning: unused variable 'p1' [-Wunused-variable]
  103 |             int p1 = 0;
      |                 ^~
regions.cpp:104:17: warning: unused variable 'p2' [-Wunused-variable]
  104 |             int p2 = 0;
      |                 ^~

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