oj.uz

Submission #299376

# Submission time Handle Problem Language Result Execution time Memory
299376 2020-09-14T19:55:25 Z mat_v Regions (IOI09_regions) C++14
45 / 100
 4242 ms 128972 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]);
    }
}

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6400 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 6 ms 6272 KB Output is correct
4 Correct 9 ms 6272 KB Output is correct
5 Correct 12 ms 6272 KB Output is correct
6 Correct 26 ms 6400 KB Output is correct
7 Correct 31 ms 6564 KB Output is correct
8 Correct 36 ms 6400 KB Output is correct
9 Correct 54 ms 6912 KB Output is correct
10 Correct 77 ms 7040 KB Output is correct
11 Correct 108 ms 7500 KB Output is correct
12 Correct 128 ms 8136 KB Output is correct
13 Correct 138 ms 8320 KB Output is correct
14 Correct 186 ms 8832 KB Output is correct
15 Correct 195 ms 11456 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2597 ms 13220 KB Output isn't correct
2 Incorrect 4156 ms 13320 KB Output isn't correct
3 Incorrect 3985 ms 15480 KB Output isn't correct
4 Correct 251 ms 8832 KB Output is correct
5 Correct 327 ms 10240 KB Output is correct
6 Incorrect 713 ms 38136 KB Output isn't correct
7 Correct 967 ms 12280 KB Output is correct
8 Incorrect 880 ms 56580 KB Output isn't correct
9 Correct 1433 ms 19704 KB Output is correct
10 Correct 2081 ms 23544 KB Output is correct
11 Correct 2206 ms 22872 KB Output is correct
12 Incorrect 1880 ms 83544 KB Output isn't correct
13 Incorrect 2349 ms 84468 KB Output isn't correct
14 Incorrect 2869 ms 100332 KB Output isn't correct
15 Incorrect 3420 ms 124140 KB Output isn't correct
16 Incorrect 4234 ms 128972 KB Output isn't correct
17 Incorrect 4242 ms 107992 KB Output isn't correct