oj.uz

Submission #287717

# Submission time Handle Problem Language Result Execution time Memory
287717 2020-08-31T22:47:00 Z NaimSS Regions (IOI09_regions) C++14
65 / 100
 8000 ms 60380 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 = 250;
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 5 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 6304 KB Output is correct
5 Correct 13 ms 6272 KB Output is correct
6 Correct 19 ms 6272 KB Output is correct
7 Correct 33 ms 6272 KB Output is correct
8 Correct 39 ms 6400 KB Output is correct
9 Correct 39 ms 6656 KB Output is correct
10 Correct 86 ms 6912 KB Output is correct
11 Correct 134 ms 7168 KB Output is correct
12 Correct 116 ms 7672 KB Output is correct
13 Correct 217 ms 7296 KB Output is correct
14 Correct 314 ms 8012 KB Output is correct
15 Correct 231 ms 9964 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3004 ms 11196 KB Output is correct
2 Correct 1732 ms 10496 KB Output is correct
3 Correct 5960 ms 12668 KB Output is correct
4 Correct 343 ms 8064 KB Output is correct
5 Correct 443 ms 9336 KB Output is correct
6 Correct 886 ms 11256 KB Output is correct
7 Correct 1544 ms 12664 KB Output is correct
8 Runtime error 4903 ms 38288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 1043 ms 45432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 6033 ms 60380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 358 ms 56440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Correct 1987 ms 17912 KB Output is correct
13 Correct 3560 ms 17956 KB Output is correct
14 Correct 3458 ms 19660 KB Output is correct
15 Execution timed out 8013 ms 21400 KB Time limit exceeded
16 Execution timed out 8032 ms 27916 KB Time limit exceeded
17 Execution timed out 8021 ms 24616 KB Time limit exceeded