oj.uz

Submission #933070

# Submission time Handle Problem Language Result Execution time Memory
933070 2024-02-25T00:53:58 Z vjudge1 Regions (IOI09_regions) C++17
30 / 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[rev[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 8 ms 1084 KB Output is correct
7 Correct 13 ms 600 KB Output is correct
8 Correct 13 ms 1004 KB Output is correct
9 Correct 24 ms 1932 KB Output is correct
10 Correct 47 ms 2904 KB Output is correct
11 Correct 49 ms 2624 KB Output is correct
12 Correct 71 ms 4416 KB Output is correct
13 Correct 104 ms 3644 KB Output is correct
14 Correct 94 ms 3896 KB Output is correct
15 Correct 110 ms 7336 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 9152 KB Output is correct
2 Correct 440 ms 8528 KB Output is correct
3 Correct 710 ms 11948 KB Output is correct
4 Incorrect 1035 ms 14296 KB Output isn't correct
5 Incorrect 1818 ms 31140 KB Output isn't correct
6 Execution timed out 8038 ms 27356 KB Time limit exceeded
7 Execution timed out 8090 ms 35764 KB Time limit exceeded
8 Execution timed out 8013 ms 93860 KB Time limit exceeded
9 Execution timed out 8087 ms 96868 KB Time limit exceeded
10 Runtime error 315 ms 131072 KB Execution killed with signal 9
11 Execution timed out 8048 ms 78148 KB Time limit exceeded
12 Execution timed out 8038 ms 101088 KB Time limit exceeded
13 Execution timed out 8012 ms 113392 KB Time limit exceeded
14 Execution timed out 8045 ms 100080 KB Time limit exceeded
15 Runtime error 325 ms 131072 KB Execution killed with signal 9
16 Runtime error 301 ms 131072 KB Execution killed with signal 9
17 Runtime error 299 ms 131072 KB Execution killed with signal 9