oj.uz

Submission #933072

# Submission time Handle Problem Language Result Execution time Memory
933072 2024-02-25T01:02: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=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<int>&)':
regions.cpp:30:17: warning: comparison of integer expressions of different signedness: 'lli' {aka 'int'} and 'std::vector<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 820 KB Output is correct
7 Correct 11 ms 600 KB Output is correct
8 Correct 20 ms 792 KB Output is correct
9 Correct 33 ms 1452 KB Output is correct
10 Correct 43 ms 1948 KB Output is correct
11 Correct 65 ms 1956 KB Output is correct
12 Correct 101 ms 3092 KB Output is correct
13 Correct 79 ms 2532 KB Output is correct
14 Correct 88 ms 2960 KB Output is correct
15 Correct 104 ms 5836 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 7408 KB Output is correct
2 Correct 526 ms 6188 KB Output is correct
3 Correct 710 ms 9500 KB Output is correct
4 Correct 1031 ms 13928 KB Output is correct
5 Correct 1800 ms 31412 KB Output is correct
6 Execution timed out 8051 ms 26816 KB Time limit exceeded
7 Execution timed out 8099 ms 35084 KB Time limit exceeded
8 Execution timed out 8058 ms 92516 KB Time limit exceeded
9 Execution timed out 8058 ms 95640 KB Time limit exceeded
10 Runtime error 337 ms 131072 KB Execution killed with signal 9
11 Execution timed out 8048 ms 76188 KB Time limit exceeded
12 Execution timed out 8028 ms 99576 KB Time limit exceeded
13 Execution timed out 8096 ms 111884 KB Time limit exceeded
14 Execution timed out 8064 ms 98176 KB Time limit exceeded
15 Runtime error 361 ms 131072 KB Execution killed with signal 9
16 Runtime error 326 ms 131072 KB Execution killed with signal 9
17 Runtime error 318 ms 131072 KB Execution killed with signal 9