oj.uz

Submission #287736

# Submission time Handle Problem Language Result Execution time Memory
287736 2020-08-31T22:56:50 Z NaimSS Regions (IOI09_regions) C++14
45 / 100
 5457 ms 131076 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 = 500;
int id[N],rev[N];
int ans[R/sq][R];

int cur=0;
void go(int v,int p,int i,int ck){
  if(H[v] == i)cur++;
  else ans[ck][H[v]]+=cur;
  for(int to : g[cur])go(to,v,i,ck);
  if(H[v]==i)cur--;  
}

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;
      go(1,-1,i,ck);
    }
  }

  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 6 ms 6272 KB Output is correct
4 Correct 8 ms 6272 KB Output is correct
5 Correct 13 ms 6272 KB Output is correct
6 Correct 20 ms 6272 KB Output is correct
7 Correct 33 ms 6272 KB Output is correct
8 Correct 33 ms 6400 KB Output is correct
9 Correct 48 ms 6764 KB Output is correct
10 Correct 82 ms 6784 KB Output is correct
11 Correct 103 ms 7168 KB Output is correct
12 Correct 168 ms 7552 KB Output is correct
13 Correct 252 ms 7296 KB Output is correct
14 Correct 388 ms 8056 KB Output is correct
15 Correct 296 ms 9856 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 115 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 111 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Incorrect 3748 ms 12572 KB Output isn't correct
4 Correct 272 ms 8056 KB Output is correct
5 Correct 376 ms 9364 KB Output is correct
6 Incorrect 1294 ms 9392 KB Output isn't correct
7 Correct 2058 ms 10488 KB Output is correct
8 Incorrect 1584 ms 14712 KB Output isn't correct
9 Correct 2591 ms 16116 KB Output is correct
10 Correct 4958 ms 19960 KB Output is correct
11 Correct 5457 ms 16504 KB Output is correct
12 Runtime error 183 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 166 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Incorrect 2683 ms 17912 KB Output isn't correct
15 Incorrect 3819 ms 21112 KB Output isn't correct
16 Incorrect 3339 ms 24616 KB Output isn't correct
17 Incorrect 3673 ms 23920 KB Output isn't correct