oj.uz

Submission #287722

# Submission time Handle Problem Language Result Execution time Memory
287722 2020-08-31T22:50:39 Z NaimSS Regions (IOI09_regions) C++14
70 / 100
 8000 ms 62140 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 = 300;
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 9 ms 6272 KB Output is correct
6 Correct 22 ms 6272 KB Output is correct
7 Correct 32 ms 6400 KB Output is correct
8 Correct 27 ms 6400 KB Output is correct
9 Correct 49 ms 6776 KB Output is correct
10 Correct 88 ms 6784 KB Output is correct
11 Correct 130 ms 7296 KB Output is correct
12 Correct 143 ms 7644 KB Output is correct
13 Correct 216 ms 7296 KB Output is correct
14 Correct 338 ms 8056 KB Output is correct
15 Correct 282 ms 9960 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2976 ms 11272 KB Output is correct
2 Correct 2559 ms 10104 KB Output is correct
3 Correct 5506 ms 12928 KB Output is correct
4 Correct 281 ms 8192 KB Output is correct
5 Correct 383 ms 9364 KB Output is correct
6 Correct 893 ms 11256 KB Output is correct
7 Correct 1328 ms 12792 KB Output is correct
8 Runtime error 4941 ms 40276 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Correct 2759 ms 19552 KB Output is correct
10 Runtime error 6375 ms 62140 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 324 ms 52672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Correct 1947 ms 18040 KB Output is correct
13 Correct 3406 ms 17812 KB Output is correct
14 Correct 4048 ms 19680 KB Output is correct
15 Execution timed out 8003 ms 21400 KB Time limit exceeded
16 Execution timed out 8099 ms 24712 KB Time limit exceeded
17 Execution timed out 8022 ms 24868 KB Time limit exceeded