oj.uz

Submission #933068

# Submission time Handle Problem Language Result Execution time Memory
933068 2024-02-25T00:48:49 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<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
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 1076 KB Output is correct
7 Correct 12 ms 600 KB Output is correct
8 Correct 16 ms 856 KB Output is correct
9 Correct 19 ms 1916 KB Output is correct
10 Correct 50 ms 2808 KB Output is correct
11 Correct 56 ms 2528 KB Output is correct
12 Correct 71 ms 4252 KB Output is correct
13 Correct 80 ms 3456 KB Output is correct
14 Correct 86 ms 3668 KB Output is correct
15 Correct 108 ms 6800 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 8576 KB Output is correct
2 Correct 489 ms 7928 KB Output is correct
3 Correct 731 ms 11240 KB Output is correct
4 Incorrect 919 ms 14044 KB Output isn't correct
5 Incorrect 1816 ms 31012 KB Output isn't correct
6 Execution timed out 8069 ms 27040 KB Time limit exceeded
7 Execution timed out 8050 ms 35012 KB Time limit exceeded
8 Execution timed out 8090 ms 92956 KB Time limit exceeded
9 Execution timed out 8071 ms 95900 KB Time limit exceeded
10 Runtime error 326 ms 131072 KB Execution killed with signal 9
11 Execution timed out 8055 ms 76548 KB Time limit exceeded
12 Execution timed out 8055 ms 99752 KB Time limit exceeded
13 Execution timed out 8064 ms 111816 KB Time limit exceeded
14 Execution timed out 8090 ms 98352 KB Time limit exceeded
15 Runtime error 310 ms 131072 KB Execution killed with signal 9
16 Runtime error 292 ms 131072 KB Execution killed with signal 9
17 Runtime error 304 ms 131072 KB Execution killed with signal 9