oj.uz

Submission #933066

# Submission time Handle Problem Language Result Execution time Memory
933066 2024-02-25T00:46:54 Z vjudge1 Regions (IOI09_regions) C++17
35 / 100
 1597 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");
    
      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 2 ms 340 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 1080 KB Output is correct
7 Correct 12 ms 1024 KB Output is correct
8 Correct 17 ms 964 KB Output is correct
9 Correct 22 ms 1916 KB Output is correct
10 Correct 39 ms 2824 KB Output is correct
11 Correct 49 ms 2500 KB Output is correct
12 Correct 63 ms 4252 KB Output is correct
13 Correct 85 ms 3472 KB Output is correct
14 Correct 83 ms 3672 KB Output is correct
15 Correct 104 ms 6764 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 8704 KB Output is correct
2 Correct 489 ms 7844 KB Output is correct
3 Correct 704 ms 11232 KB Output is correct
4 Correct 1597 ms 128968 KB Output is correct
5 Runtime error 56 ms 131072 KB Execution killed with signal 9
6 Runtime error 66 ms 131072 KB Execution killed with signal 9
7 Runtime error 61 ms 131072 KB Execution killed with signal 9
8 Runtime error 65 ms 131072 KB Execution killed with signal 9
9 Runtime error 78 ms 131072 KB Execution killed with signal 9
10 Runtime error 77 ms 131072 KB Execution killed with signal 9
11 Runtime error 84 ms 131072 KB Execution killed with signal 9
12 Runtime error 84 ms 131072 KB Execution killed with signal 9
13 Runtime error 81 ms 131072 KB Execution killed with signal 9
14 Runtime error 86 ms 131072 KB Execution killed with signal 9
15 Runtime error 84 ms 131072 KB Execution killed with signal 9
16 Runtime error 85 ms 131072 KB Execution killed with signal 9
17 Runtime error 79 ms 131072 KB Execution killed with signal 9