oj.uz

Submission #287702

# Submission time Handle Problem Language Result Execution time Memory
287702 2020-08-31T22:38:18 Z NaimSS Regions (IOI09_regions) C++14
75 / 100
 8000 ms 60772 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 = 325;
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 4 ms 6272 KB Output is correct
3 Correct 6 ms 6272 KB Output is correct
4 Correct 9 ms 6272 KB Output is correct
5 Correct 11 ms 6272 KB Output is correct
6 Correct 18 ms 6272 KB Output is correct
7 Correct 36 ms 6272 KB Output is correct
8 Correct 43 ms 6400 KB Output is correct
9 Correct 70 ms 6656 KB Output is correct
10 Correct 109 ms 6912 KB Output is correct
11 Correct 122 ms 7168 KB Output is correct
12 Correct 187 ms 7552 KB Output is correct
13 Correct 242 ms 7296 KB Output is correct
14 Correct 390 ms 7936 KB Output is correct
15 Correct 282 ms 9856 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3086 ms 11128 KB Output is correct
2 Correct 2711 ms 10236 KB Output is correct
3 Correct 5724 ms 12596 KB Output is correct
4 Correct 283 ms 8064 KB Output is correct
5 Correct 377 ms 9464 KB Output is correct
6 Correct 878 ms 11256 KB Output is correct
7 Correct 1439 ms 12280 KB Output is correct
8 Runtime error 4738 ms 39584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Correct 2819 ms 16120 KB Output is correct
10 Runtime error 6075 ms 60772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Correct 5683 ms 16424 KB Output is correct
12 Correct 1865 ms 17860 KB Output is correct
13 Correct 3274 ms 17808 KB Output is correct
14 Correct 3564 ms 19652 KB Output is correct
15 Execution timed out 8039 ms 21424 KB Time limit exceeded
16 Execution timed out 8099 ms 24704 KB Time limit exceeded
17 Execution timed out 8074 ms 24572 KB Time limit exceeded