oj.uz

Submission #933063

# Submission time Handle Problem Language Result Execution time Memory
933063 2024-02-25T00:37:03 Z vjudge1 Regions (IOI09_regions) C++17
0 / 100
 1459 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
2 Execution timed out 0 ms 344 KB Time limit exceeded (wall clock)
3 Execution timed out 0 ms 344 KB Time limit exceeded (wall clock)
4 Execution timed out 0 ms 344 KB Time limit exceeded (wall clock)
5 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
6 Execution timed out 2 ms 856 KB Time limit exceeded (wall clock)
7 Execution timed out 1 ms 600 KB Time limit exceeded (wall clock)
8 Execution timed out 1 ms 856 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 1880 KB Time limit exceeded (wall clock)
10 Execution timed out 10 ms 2688 KB Time limit exceeded (wall clock)
11 Execution timed out 10 ms 2392 KB Time limit exceeded (wall clock)
12 Execution timed out 23 ms 4316 KB Time limit exceeded (wall clock)
13 Execution timed out 19 ms 3416 KB Time limit exceeded (wall clock)
14 Execution timed out 22 ms 3672 KB Time limit exceeded (wall clock)
15 Execution timed out 22 ms 6544 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 41 ms 8456 KB Time limit exceeded (wall clock)
2 Execution timed out 39 ms 7700 KB Time limit exceeded (wall clock)
3 Execution timed out 50 ms 11232 KB Time limit exceeded (wall clock)
4 Execution timed out 1459 ms 128660 KB Time limit exceeded (wall clock)
5 Runtime error 56 ms 131072 KB Execution killed with signal 9
6 Runtime error 63 ms 131072 KB Execution killed with signal 9
7 Runtime error 66 ms 131072 KB Execution killed with signal 9
8 Runtime error 73 ms 131072 KB Execution killed with signal 9
9 Runtime error 85 ms 131072 KB Execution killed with signal 9
10 Runtime error 78 ms 131072 KB Execution killed with signal 9
11 Runtime error 85 ms 131072 KB Execution killed with signal 9
12 Runtime error 86 ms 131072 KB Execution killed with signal 9
13 Runtime error 82 ms 131072 KB Execution killed with signal 9
14 Runtime error 89 ms 131072 KB Execution killed with signal 9
15 Runtime error 88 ms 131072 KB Execution killed with signal 9
16 Runtime error 84 ms 131072 KB Execution killed with signal 9
17 Runtime error 89 ms 131072 KB Execution killed with signal 9