oj.uz

Submission #287714

# Submission time Handle Problem Language Result Execution time Memory
287714 2020-08-31T22:45:14 Z NaimSS Regions (IOI09_regions) C++14
44 / 100
 8000 ms 85476 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 = 130;
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
14.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 22 ms 6272 KB Output is correct
7 Correct 30 ms 6272 KB Output is correct
8 Correct 40 ms 6312 KB Output is correct
9 Correct 47 ms 6656 KB Output is correct
10 Correct 97 ms 6896 KB Output is correct
11 Correct 130 ms 7168 KB Output is correct
12 Correct 161 ms 7640 KB Output is correct
13 Correct 216 ms 7404 KB Output is correct
14 Correct 163 ms 8952 KB Output is correct
15 Runtime error 2732 ms 24400 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 1748 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Correct 956 ms 10992 KB Output is correct
3 Runtime error 4910 ms 30448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 298 ms 9976 KB Output is correct
5 Correct 379 ms 9468 KB Output is correct
6 Correct 808 ms 11256 KB Output is correct
7 Correct 1153 ms 14328 KB Output is correct
8 Correct 5839 ms 19140 KB Output is correct
9 Runtime error 1280 ms 60792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 7768 ms 84020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 580 ms 75896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 632 ms 64632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Execution timed out 8089 ms 31936 KB Time limit exceeded
14 Runtime error 1749 ms 71656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 5254 ms 85476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Execution timed out 8019 ms 35216 KB Time limit exceeded
17 Execution timed out 8102 ms 31440 KB Time limit exceeded