oj.uz

Submission #287700

# Submission time Handle Problem Language Result Execution time Memory
287700 2020-08-31T22:37:02 Z NaimSS Regions (IOI09_regions) C++14
85 / 100
 8000 ms 24700 KB 
#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end());
#define sz(v) (int)v.size()
//#define int long long
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
#define left sefude
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
#define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl; 
typedef long long ll;
typedef pair<int,int> pii;

inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll a,ll b,ll m){
    if(b==0LL) return 1LL;
    if(b==1LL) return mod(a,m);
    ll k = mod(exp(a,b/2,m),m);
    if(b&1LL){
        return mod(a*mod(k*k,m),m);
    }
    else return mod(k*k,m);
}

const int N = 200100;
const int R = 25100;

vi g[N];
vi here[R];
vi tempo[R];
int tin[N],tout[N],t;
int H[N];
int ar[N];
void dfs(int v){
  tin[v] = ++t;ar[t] = H[v];
  tempo[H[v]].pb(t);  
  for(int to : g[v])dfs(to);
  tout[v] = t;
}
int cnt[N];
const int sq = 800;
int id[N],rev[N];
int ans[R/sq][R];
int32_t main(){
  fastio;
  int n,r,q;
  cin>>n>>r>>q;
  for(int i=1;i<=n;i++){
    if(i == 1){
      cin >> H[i];
    }else{
      int p;
      cin >> p >> H[i];
      g[p].pb(i);
    }
    here[H[i]].pb(i);
    cnt[H[i]]++;
  }
  dfs(1);
  rep(i,0,R)sort(all(tempo[i]));
  int ck = 0;
  for(int i=1;i<=r;i++){
    if(cnt[i]>=sq){
      id[++ck] = i;
      rev[i] = ck;

      for(int k : here[i]){
        for(int tt = tin[k];tt<=tout[k];tt++){
          ans[ck][ar[tt]]++;
        }
      }

    }
  }

  while(q--){
    int r1,r2;
    cin >> r1 >> r2;
    if(rev[r1] > 0){
      cout << ans[rev[r1]][r2]<< endl;
    }else{
      int res=0;
      for(int k : here[r1]){
        res+=upper_bound(all(tempo[r2]),tout[k]) - lower_bound(all(tempo[r2]),tin[k]);
      }
      cout << res << endl;
    }
    cout.flush();
  }
  // math -> gcd it all
  // Did u check N=1? Did you switch N,M?
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6272 KB Output is correct
2 Correct 5 ms 6272 KB Output is correct
3 Correct 7 ms 6272 KB Output is correct
4 Correct 9 ms 6272 KB Output is correct
5 Correct 13 ms 6272 KB Output is correct
6 Correct 23 ms 6272 KB Output is correct
7 Correct 27 ms 6400 KB Output is correct
8 Correct 36 ms 6400 KB Output is correct
9 Correct 51 ms 6656 KB Output is correct
10 Correct 87 ms 6784 KB Output is correct
11 Correct 139 ms 7168 KB Output is correct
12 Correct 159 ms 7672 KB Output is correct
13 Correct 207 ms 7416 KB Output is correct
14 Correct 285 ms 7968 KB Output is correct
15 Correct 285 ms 9976 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3075 ms 11000 KB Output is correct
2 Correct 2801 ms 10124 KB Output is correct
3 Correct 5872 ms 12664 KB Output is correct
4 Correct 324 ms 8064 KB Output is correct
5 Correct 394 ms 9468 KB Output is correct
6 Correct 1816 ms 9344 KB Output is correct
7 Correct 2086 ms 10488 KB Output is correct
8 Correct 1562 ms 14584 KB Output is correct
9 Correct 2988 ms 16112 KB Output is correct
10 Correct 5436 ms 19960 KB Output is correct
11 Correct 5723 ms 16420 KB Output is correct
12 Correct 2140 ms 17856 KB Output is correct
13 Correct 3345 ms 17804 KB Output is correct
14 Correct 3929 ms 19128 KB Output is correct
15 Execution timed out 8064 ms 21396 KB Time limit exceeded
16 Execution timed out 8067 ms 24700 KB Time limit exceeded
17 Execution timed out 8038 ms 24448 KB Time limit exceeded