oj.uz

Submission #287687

# Submission time Handle Problem Language Result Execution time Memory
287687 2020-08-31T22:19:22 Z NaimSS Regions (IOI09_regions) C++14
0 / 100
 8000 ms 24688 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 = 500;
int id[N],rev[N];
int ans[N/sq][N];
int32_t main(){
  //fastio;
  int n,r,q;
  //cin>>n>>r>>q;
  scanf("%d%d%d",&n,&r,&q);
  for(int i=1;i<=n;i++){
    if(i == 1){
      //cin >> H[i];
      scanf("%d",&H[i]);
    }else{
      int p;
      //cin >> p >> H[i];
      scanf("%d%d",&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;
    scanf("%d%d",&r1,&r2);
    if(rev[r1] > 0){
      //cout << ans[rev[r1]][r2]<< endl;
      printf("%d\n",ans[rev[r1]][r2]);
    }else{
      int res=0;
      for(int k : here[r1]){
        res+=upper_bound(all(tempo[r2]),tout[k]) - lower_bound(all(tempo[r2]),tin[k]);
      }
      printf("%d\n",res);
    }
  }
  // math -> gcd it all
  // Did u check N=1? Did you switch N,M?
}

Compilation message

regions.cpp: In function 'int32_t main()':
regions.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |   scanf("%d%d%d",&n,&r,&q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:67:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |       scanf("%d",&H[i]);
      |       ~~~~~^~~~~~~~~~~~
regions.cpp:71:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |       scanf("%d%d",&p,&H[i]);
      |       ~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |     scanf("%d%d",&r1,&r2);
      |     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4 ms 6272 KB Time limit exceeded (wall clock)
2 Execution timed out 4 ms 6272 KB Time limit exceeded (wall clock)
3 Execution timed out 4 ms 6400 KB Time limit exceeded (wall clock)
4 Execution timed out 4 ms 6272 KB Time limit exceeded (wall clock)
5 Execution timed out 4 ms 6272 KB Time limit exceeded (wall clock)
6 Execution timed out 4 ms 6272 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 6272 KB Time limit exceeded (wall clock)
8 Execution timed out 5 ms 6400 KB Time limit exceeded (wall clock)
9 Execution timed out 6 ms 6656 KB Time limit exceeded (wall clock)
10 Execution timed out 8 ms 6784 KB Time limit exceeded (wall clock)
11 Execution timed out 11 ms 7040 KB Time limit exceeded (wall clock)
12 Execution timed out 12 ms 7552 KB Time limit exceeded (wall clock)
13 Execution timed out 16 ms 7296 KB Time limit exceeded (wall clock)
14 Execution timed out 18 ms 7936 KB Time limit exceeded (wall clock)
15 Execution timed out 20 ms 9856 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 721 ms 11080 KB Time limit exceeded (wall clock)
2 Execution timed out 186 ms 10064 KB Time limit exceeded (wall clock)
3 Execution timed out 2199 ms 12664 KB Time limit exceeded (wall clock)
4 Execution timed out 19 ms 8064 KB Time limit exceeded (wall clock)
5 Execution timed out 20 ms 9336 KB Time limit exceeded (wall clock)
6 Execution timed out 138 ms 9976 KB Time limit exceeded (wall clock)
7 Execution timed out 49 ms 10360 KB Time limit exceeded (wall clock)
8 Execution timed out 195 ms 14712 KB Time limit exceeded (wall clock)
9 Execution timed out 92 ms 15992 KB Time limit exceeded (wall clock)
10 Execution timed out 86 ms 20012 KB Time limit exceeded (wall clock)
11 Execution timed out 111 ms 16376 KB Time limit exceeded (wall clock)
12 Execution timed out 332 ms 17784 KB Time limit exceeded (wall clock)
13 Execution timed out 1089 ms 17712 KB Time limit exceeded (wall clock)
14 Execution timed out 1190 ms 19532 KB Time limit exceeded (wall clock)
15 Execution timed out 4447 ms 21272 KB Time limit exceeded (wall clock)
16 Execution timed out 8076 ms 24688 KB Time limit exceeded
17 Execution timed out 8089 ms 24592 KB Time limit exceeded