oj.uz

Submission #299094

# Submission time Handle Problem Language Result Execution time Memory
299094 2020-09-14T13:23:36 Z mat_v Regions (IOI09_regions) C++14
5 / 100
 8000 ms 131076 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9856 KB Output is correct
2 Correct 7 ms 9856 KB Output is correct
3 Correct 9 ms 9984 KB Output is correct
4 Correct 12 ms 10496 KB Output is correct
5 Correct 19 ms 12160 KB Output is correct
6 Runtime error 41 ms 26360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 48 ms 25592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 55 ms 26104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 72 ms 27896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 169 ms 28792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 239 ms 28280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 256 ms 30968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 430 ms 29688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 514 ms 29304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 359 ms 35832 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 1348 ms 37196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 1870 ms 35528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 1051 ms 43644 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 525 ms 60536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 410 ms 73080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 1054 ms 87928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 2067 ms 114016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 1418 ms 127316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 6727 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 3064 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Execution timed out 8053 ms 120960 KB Time limit exceeded
12 Execution timed out 8045 ms 66204 KB Time limit exceeded
13 Runtime error 8034 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Execution timed out 8077 ms 83112 KB Time limit exceeded
15 Runtime error 5624 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 3560 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 3621 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)