Submission #299094

#	Time	Username	Problem	Language	Result	Execution time	Memory
299094		mat_v	Regions (IOI09_regions)	C++14	5 / 100	8077 ms	131076 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);
    }
}

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 >= -1)veci[i] = 1;
        for(auto c:boja[i]){
            if(veci[i]){
                slika[br] = c;
                gde[c] = br;
                br++;
            }
        }
    }
    dfs(1);
    ff(i,1,br - 1){
        int tr = slika[i];
        color(cale[tr], tr, i, 1);
        color(tr, cale[tr], i, 0);
        kolko[i][niz[tr]][0]--;
    }
    while(q--){
        int r1,r2;
        cin >> r1 >> r2;
        if(veci[r1] || veci[r2]){
            if(veci[r1]){
                ll ans = 0;
                for(auto c:boja[r1]){
                    ans += kolko[gde[c]][r2][0];
                }
                cout << ans << endl;
            }
            else{
                ll ans = 0;
                for(auto c:boja[r2]){
                    ans += kolko[gde[c]][r1][1];
                }
            }
        }
        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:50:5: note: in expansion of macro 'ff'
   50 |     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:63:5: note: in expansion of macro 'ff'
   63 |     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:75:5: note: in expansion of macro 'ff'
   75 |     ff(i,1,br - 1){
      |     ^~
regions.cpp:100:17: warning: unused variable 'p1' [-Wunused-variable]
  100 |             int p1 = 0;
      |                 ^~
regions.cpp:101:17: warning: unused variable 'p2' [-Wunused-variable]
  101 |             int p2 = 0;
      |                 ^~

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