oj.uz

Submission #287675

# Submission time Handle Problem Language Result Execution time Memory
287675 2020-08-31T22:12:21 Z NaimSS Regions (IOI09_regions) C++14
80 / 100
 8000 ms 25264 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];

void dfs(int v){
  tin[v] = ++t;
  tempo[H[v]].pb(t);  
  for(int to : g[v])dfs(to);
  tout[v] = t;
}
int cnt[N];
const int sq = 450;
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 j=1;j<=r;j++){
        if(i == j)ans[ck][j]=0;
        else{

          for(int k : here[i]){
            ans[ck][j]+=upper_bound(all(tempo[j]),tout[k]) - lower_bound(all(tempo[j]),tin[k]);
          }

        }
      }

    }
  }

  while(q--){
    int r1,r2;
    cin >> r1 >> r2;
    if(rev[r1] > 0){
      cout << ans[rev[r1]][r2]<< endl;
      cout.flush();
    }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 8 ms 6272 KB Output is correct
5 Correct 11 ms 6272 KB Output is correct
6 Correct 26 ms 6272 KB Output is correct
7 Correct 31 ms 6272 KB Output is correct
8 Correct 47 ms 6400 KB Output is correct
9 Correct 52 ms 6656 KB Output is correct
10 Correct 90 ms 6904 KB Output is correct
11 Correct 137 ms 7160 KB Output is correct
12 Correct 148 ms 7552 KB Output is correct
13 Correct 197 ms 7416 KB Output is correct
14 Correct 318 ms 7928 KB Output is correct
15 Correct 294 ms 9848 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2545 ms 10860 KB Output is correct
2 Correct 2769 ms 9976 KB Output is correct
3 Correct 3821 ms 12280 KB Output is correct
4 Correct 308 ms 7936 KB Output is correct
5 Correct 462 ms 9336 KB Output is correct
6 Correct 3720 ms 11176 KB Output is correct
7 Correct 2936 ms 10808 KB Output is correct
8 Correct 5980 ms 18976 KB Output is correct
9 Correct 2880 ms 15520 KB Output is correct
10 Execution timed out 8048 ms 25264 KB Time limit exceeded
11 Correct 5633 ms 15636 KB Output is correct
12 Correct 7517 ms 17528 KB Output is correct
13 Correct 7518 ms 17468 KB Output is correct
14 Execution timed out 8036 ms 17936 KB Time limit exceeded
15 Execution timed out 8018 ms 21096 KB Time limit exceeded
16 Correct 7863 ms 24620 KB Output is correct
17 Execution timed out 8070 ms 24844 KB Time limit exceeded