oj.uz

Submission #933059

# Submission time Handle Problem Language Result Execution time Memory
933059 2024-02-25T00:25:48 Z vjudge1 Regions (IOI09_regions) C++17
0 / 100
 328 ms 131072 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define deb(x) ;
using lli=long long int;
 
 
#ifndef LOCAL
    #define endl '\n'
#endif
 
vector<lli> ch;
lli aux=0;
vector<vector<lli>> sons;
vector<pair<lli,lli>> ranges;
void dfs(lli n){
  ch[n]=aux;
  lli ini=aux;
  aux++;
  for(lli x: sons[n]){
    dfs(x);
  }
  ranges[n]={ini, aux-1};
}
 vector<vector<lli>> ans;
 vector<lli> regions;
void solvefirstcase(lli n, vector<lli> &act){
  for(lli i=0; i<act.size(); ++i){
    ans[i][regions[n]]+=act[i];
  }
  act[regions[n]]++;
  for(lli x: sons[n]){
    solvefirstcase(x,act );
  }
  act[regions[n]]--;
}

struct segtree{
  segtree *left, *right;
  multiset<lli> values;
  lli l,r;
  segtree(lli a, lli b): l(a), r(b){
    lli m=(l+r)/2;
    if(l!=r){
      left=new segtree(l, m);
      right=new segtree(m+1, r);
    }
  }
  void insert(lli a, lli b, lli v){
    if(a<=l && r<=b){
      values.insert(v);
      return;
    }
    if(r<=a || b<=l){
      return;
    }
    left->insert(a,b,v);
    right->insert(a,b,v);
  }
  lli query(lli x, lli v){
    lli ans=values.count(v);
    if(l==r){
      return ans;
    }
    lli m=(l+r)/2;
    if(x<=m){
      ans+=left->query(x,v);
    }
    else{
      ans+=right->query(x,v);
    }
    return ans;
  }
};


void solve(){
    lli n,r,k;
    cin>>n>>r>>k;
    regions.resize(n);
    cin>>regions[0];
    regions[0]--;
    sons.resize(n);
    vector<vector<lli>> members(r);
    members[regions[0]].pb(0);
    for(lli i=1; i<n; ++i){
      deb(i);
      lli s;
      cin>>s>>regions[i];
      s--;
      regions[i]--;
      deb("hi");
      members[regions[i]].pb(i);
      deb("Hi2");
      sons[s].pb(i);
      deb("HI3");
    }
    ch.resize(n);
    ranges.resize(n);
    deb("hi");
    dfs(0);
    deb("hi");
    if(r<=500){
      ans.resize(r, vector<lli> (r,0));
      vector<lli> act (r,0);
      solvefirstcase(0, act);
      for(lli i=0; i<k; ++i){
        lli a,b;
        cin>>a>>b;
        a--;
        b--;
        cout<<ans[a][b]<<endl;
      }
    }
    else{
      segtree tree(0, n);
      for(lli i=0; i<n; ++i){
        tree.insert(ranges[i].first, ranges[i].second, regions[i]);
      }
      for(lli i=0; i<k; ++i){
        lli a,b;
        cin>>a>>b;
        a--;
        b--;
        lli ans=0;
        for(lli x: members[b]){
          ans+=tree.query(x, a);
        }
        cout<<ans<<endl;
      }
    }
}
 
 
int main(){
  ios::ios_base::sync_with_stdio(0);
  cin.tie(0);
  #ifdef LOCAL
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
  #endif
  lli t=1;
// cin>>t;
  while(t--){
    solve();
  }
}

Compilation message

regions.cpp: In function 'void solvefirstcase(lli, std::vector<long long int>&)':
regions.cpp:28:17: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(lli i=0; i<act.size(); ++i){
      |                ~^~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 0 ms 344 KB Time limit exceeded (wall clock)
2 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
3 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
4 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
5 Execution timed out 0 ms 344 KB Time limit exceeded (wall clock)
6 Execution timed out 1 ms 856 KB Time limit exceeded (wall clock)
7 Execution timed out 1 ms 600 KB Time limit exceeded (wall clock)
8 Execution timed out 1 ms 856 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 1880 KB Time limit exceeded (wall clock)
10 Execution timed out 10 ms 2648 KB Time limit exceeded (wall clock)
11 Execution timed out 10 ms 2392 KB Time limit exceeded (wall clock)
12 Execution timed out 27 ms 4184 KB Time limit exceeded (wall clock)
13 Execution timed out 27 ms 3416 KB Time limit exceeded (wall clock)
14 Execution timed out 15 ms 3672 KB Time limit exceeded (wall clock)
15 Execution timed out 29 ms 6656 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 40 ms 8536 KB Time limit exceeded (wall clock)
2 Execution timed out 40 ms 7808 KB Time limit exceeded (wall clock)
3 Execution timed out 62 ms 11080 KB Time limit exceeded (wall clock)
4 Execution timed out 25 ms 13912 KB Time limit exceeded (wall clock)
5 Execution timed out 64 ms 30772 KB Time limit exceeded (wall clock)
6 Execution timed out 50 ms 27020 KB Time limit exceeded (wall clock)
7 Execution timed out 69 ms 34992 KB Time limit exceeded (wall clock)
8 Execution timed out 227 ms 92964 KB Time limit exceeded (wall clock)
9 Execution timed out 203 ms 95868 KB Time limit exceeded (wall clock)
10 Runtime error 328 ms 131072 KB Execution killed with signal 9
11 Execution timed out 160 ms 76924 KB Time limit exceeded (wall clock)
12 Execution timed out 243 ms 99880 KB Time limit exceeded (wall clock)
13 Execution timed out 251 ms 111944 KB Time limit exceeded (wall clock)
14 Execution timed out 206 ms 98332 KB Time limit exceeded (wall clock)
15 Runtime error 305 ms 131072 KB Execution killed with signal 9
16 Runtime error 311 ms 131072 KB Execution killed with signal 9
17 Runtime error 294 ms 131072 KB Execution killed with signal 9