oj.uz

Submission #299378

# Submission time Handle Problem Language Result Execution time Memory
299378 2020-09-14T19:58:19 Z mat_v Regions (IOI09_regions) C++14
0 / 100
 4278 ms 128888 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define maxn 200005

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int dlt = 500;
int t = 0;

int n,r,q;
vector<int> graf[maxn];
int cnt[maxn];
int cale[maxn], niz[maxn];
int slika[maxn];
int rev[maxn];
int atm[maxn];
int in[maxn], out[maxn];
int dole[25010][505];
int gore[25010][505];
vector<pii> all[25005];
vector<int> ins[25005];
int br;


void dfs(int x){
    in[x] = ++t;
    atm[niz[x]]++;
    if(rev[niz[x]]){
        ff(i,1,r){
            dole[i][rev[niz[x]]] += atm[i];
        }
        dole[niz[x]][rev[niz[x]]]--;
        gore[niz[x]][rev[niz[x]]]--;
    }
    ff(i,1,br){
        gore[niz[x]][i] += atm[rev[i]];
    }
    for(auto c:graf[x]){
        if(c == cale[x])continue;
        dfs(c);
    }
    atm[niz[x]]--;
    out[x] = t;
    if(!rev[niz[x]]){
        all[niz[x]].pb({in[x], -1});
        all[niz[x]].pb({out[x], 1});
        ins[niz[x]].pb(in[x] + 1);
    }
}

int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> r >> q;
    ff(i,1,n){
        if(i == 1){
            cin >> niz[i];
            continue;
        }
        cin >> cale[i] >> niz[i];
        graf[i].pb(cale[i]);
        graf[cale[i]].pb(i);
        cnt[niz[i]]++;
    }
    ff(i,1,r){
        if(cnt[i] >= dlt){
            slika[i] = ++br;
            rev[br] = i;
        }
    }
    dfs(1);
    ff(i,1,r){
        sort(all[i].begin(), all[i].end());
        sort(ins[i].begin(), ins[i].end());
    }
    while(q--){
        int r1,r2;
        cin >> r1 >> r2;
        if(rev[r1]){
            cout << dole[r2][rev[r1]] << endl;
            continue;
        }
        if(rev[r2]){
            cout << gore[r1][rev[r2]] << endl;
            continue;
        }
        int ans = 0;
        for(int i=0, j=0; i<all[r1].size();i++){
            while(j<ins[r2].size() && ins[r2][j] <= all[r1][i].xx)j++;
            ans += j*all[r1][i].yy;
        }
        cout << ans << endl;

    }
    return 0;
}

Compilation message

regions.cpp: In function 'void dfs(int)':
regions.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
regions.cpp:44:9: note: in expansion of macro 'ff'
   44 |         ff(i,1,r){
      |         ^~
regions.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #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,br){
      |     ^~
regions.cpp: In function 'int main()':
regions.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
regions.cpp:71:5: note: in expansion of macro 'ff'
   71 |     ff(i,1,n){
      |     ^~
regions.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
regions.cpp:81:5: note: in expansion of macro 'ff'
   81 |     ff(i,1,r){
      |     ^~
regions.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
regions.cpp:88:5: note: in expansion of macro 'ff'
   88 |     ff(i,1,r){
      |     ^~
regions.cpp:104:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for(int i=0, j=0; i<all[r1].size();i++){
      |                           ~^~~~~~~~~~~~~~~
regions.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             while(j<ins[r2].size() && ins[r2][j] <= all[r1][i].xx)j++;
      |                   ~^~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6272 KB Output isn't correct
2 Incorrect 5 ms 6272 KB Output isn't correct
3 Incorrect 6 ms 6272 KB Output isn't correct
4 Incorrect 8 ms 6272 KB Output isn't correct
5 Incorrect 11 ms 6272 KB Output isn't correct
6 Incorrect 23 ms 6400 KB Output isn't correct
7 Incorrect 28 ms 6400 KB Output isn't correct
8 Incorrect 35 ms 6476 KB Output isn't correct
9 Incorrect 52 ms 7032 KB Output isn't correct
10 Incorrect 50 ms 7040 KB Output isn't correct
11 Incorrect 112 ms 7424 KB Output isn't correct
12 Incorrect 123 ms 8064 KB Output isn't correct
13 Incorrect 141 ms 8364 KB Output isn't correct
14 Incorrect 119 ms 8884 KB Output isn't correct
15 Incorrect 234 ms 11392 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2285 ms 13216 KB Output isn't correct
2 Incorrect 3948 ms 13328 KB Output isn't correct
3 Incorrect 4278 ms 15492 KB Output isn't correct
4 Incorrect 256 ms 8832 KB Output isn't correct
5 Incorrect 496 ms 10340 KB Output isn't correct
6 Incorrect 689 ms 38036 KB Output isn't correct
7 Incorrect 1104 ms 12280 KB Output isn't correct
8 Incorrect 1056 ms 56696 KB Output isn't correct
9 Incorrect 1464 ms 19776 KB Output isn't correct
10 Incorrect 2021 ms 23688 KB Output isn't correct
11 Incorrect 2108 ms 22868 KB Output isn't correct
12 Incorrect 1763 ms 83572 KB Output isn't correct
13 Incorrect 2272 ms 84340 KB Output isn't correct
14 Incorrect 2887 ms 100332 KB Output isn't correct
15 Incorrect 3489 ms 124144 KB Output isn't correct
16 Incorrect 3777 ms 128888 KB Output isn't correct
17 Incorrect 4165 ms 108012 KB Output isn't correct