oj.uz

Submission #933062

# Submission time Handle Problem Language Result Execution time Memory
933062 2024-02-25T00:34:24 Z vjudge1 Regions (IOI09_regions) C++17
0 / 100
 1450 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 1 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 1 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 2 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 12 ms 2648 KB Time limit exceeded (wall clock)
11 Execution timed out 11 ms 2392 KB Time limit exceeded (wall clock)
12 Execution timed out 20 ms 4184 KB Time limit exceeded (wall clock)
13 Execution timed out 24 ms 3668 KB Time limit exceeded (wall clock)
14 Execution timed out 18 ms 3540 KB Time limit exceeded (wall clock)
15 Execution timed out 23 ms 7008 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 41 ms 8448 KB Time limit exceeded (wall clock)
2 Execution timed out 43 ms 7776 KB Time limit exceeded (wall clock)
3 Execution timed out 54 ms 11244 KB Time limit exceeded (wall clock)
4 Execution timed out 1450 ms 128668 KB Time limit exceeded (wall clock)
5 Runtime error 59 ms 131072 KB Execution killed with signal 9
6 Runtime error 65 ms 131072 KB Execution killed with signal 9
7 Runtime error 64 ms 131072 KB Execution killed with signal 9
8 Runtime error 72 ms 131072 KB Execution killed with signal 9
9 Runtime error 92 ms 131072 KB Execution killed with signal 9
10 Runtime error 90 ms 131072 KB Execution killed with signal 9
11 Runtime error 96 ms 131072 KB Execution killed with signal 9
12 Runtime error 101 ms 131072 KB Execution killed with signal 9
13 Runtime error 90 ms 131072 KB Execution killed with signal 9
14 Runtime error 107 ms 131072 KB Execution killed with signal 9
15 Runtime error 98 ms 131072 KB Execution killed with signal 9
16 Runtime error 93 ms 131072 KB Execution killed with signal 9
17 Runtime error 96 ms 131072 KB Execution killed with signal 9