oj.uz

Submission #933071

# Submission time Handle Problem Language Result Execution time Memory
933071 2024-02-25T00:57:38 Z vjudge1 Regions (IOI09_regions) C++17
40 / 100
 8000 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<lli> rev;
vector<pair<lli,lli>> ranges;
void dfs(lli n){
  ch[n]=aux;
  rev[aux]=n;
  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);
    rev.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(ch[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:30: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]
   30 |   for(lli i=0; i<act.size(); ++i){
      |                ~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 9 ms 1088 KB Output is correct
7 Correct 20 ms 788 KB Output is correct
8 Correct 15 ms 856 KB Output is correct
9 Correct 23 ms 1952 KB Output is correct
10 Correct 43 ms 2904 KB Output is correct
11 Correct 50 ms 2640 KB Output is correct
12 Correct 62 ms 4436 KB Output is correct
13 Correct 94 ms 3644 KB Output is correct
14 Correct 72 ms 3924 KB Output is correct
15 Correct 98 ms 7076 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 9160 KB Output is correct
2 Correct 566 ms 8484 KB Output is correct
3 Correct 718 ms 11936 KB Output is correct
4 Correct 983 ms 15656 KB Output is correct
5 Correct 1720 ms 33472 KB Output is correct
6 Execution timed out 8028 ms 29792 KB Time limit exceeded
7 Execution timed out 8080 ms 38860 KB Time limit exceeded
8 Execution timed out 8048 ms 98056 KB Time limit exceeded
9 Execution timed out 8026 ms 104364 KB Time limit exceeded
10 Runtime error 304 ms 131072 KB Execution killed with signal 9
11 Execution timed out 8084 ms 87548 KB Time limit exceeded
12 Execution timed out 8073 ms 110044 KB Time limit exceeded
13 Execution timed out 8077 ms 122388 KB Time limit exceeded
14 Execution timed out 8053 ms 109420 KB Time limit exceeded
15 Runtime error 297 ms 131072 KB Execution killed with signal 9
16 Runtime error 296 ms 131072 KB Execution killed with signal 9
17 Runtime error 290 ms 131072 KB Execution killed with signal 9