oj.uz

Submission #287698

# Submission time Handle Problem Language Result Execution time Memory
287698 2020-08-31T22:34:16 Z NaimSS Regions (IOI09_regions) C++14
85 / 100
 8000 ms 24716 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[N/sq][N];
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 5 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 6 ms 6272 KB Output is correct
4 Correct 10 ms 6272 KB Output is correct
5 Correct 13 ms 6272 KB Output is correct
6 Correct 21 ms 6272 KB Output is correct
7 Correct 32 ms 6272 KB Output is correct
8 Correct 39 ms 6400 KB Output is correct
9 Correct 44 ms 6656 KB Output is correct
10 Correct 77 ms 6912 KB Output is correct
11 Correct 135 ms 7288 KB Output is correct
12 Correct 157 ms 7672 KB Output is correct
13 Correct 212 ms 7416 KB Output is correct
14 Correct 286 ms 8012 KB Output is correct
15 Correct 268 ms 9956 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2974 ms 11068 KB Output is correct
2 Correct 2675 ms 10148 KB Output is correct
3 Correct 5640 ms 12932 KB Output is correct
4 Correct 331 ms 8064 KB Output is correct
5 Correct 418 ms 9464 KB Output is correct
6 Correct 1480 ms 9976 KB Output is correct
7 Correct 1953 ms 10488 KB Output is correct
8 Correct 1609 ms 14712 KB Output is correct
9 Correct 2760 ms 16120 KB Output is correct
10 Correct 5154 ms 19960 KB Output is correct
11 Correct 5669 ms 16436 KB Output is correct
12 Correct 1935 ms 17864 KB Output is correct
13 Correct 3375 ms 17916 KB Output is correct
14 Correct 3974 ms 19664 KB Output is correct
15 Execution timed out 8029 ms 21420 KB Time limit exceeded
16 Execution timed out 8032 ms 24704 KB Time limit exceeded
17 Execution timed out 8080 ms 24716 KB Time limit exceeded