oj.uz

Submission #476983

# Submission time Handle Problem Language Result Execution time Memory
476983 2021-09-29T16:28:53 Z urosk Regions (IOI09_regions) C++14
30 / 100
 3532 ms 131076 KB 
// __builtin_popcount(x) broj bitova
// __builtin_popcountll(x) long long
#define here cerr<<"---------------------------\n"
#include "bits/stdc++.h"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define rall(a) a.begin(),a.end(),greater<int>()
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}

using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

void setIO(string inoutname)
{
	freopen((inoutname+".in").c_str(),"r",stdin);
    	freopen((inoutname+".out").c_str(),"w",stdout);
}
#define mod 1
ll gcd(ll a, ll b)
{
   if(b==0) return a;
   if(a==0) return b;
   if(a>=b)  return gcd(a%b,b);
   return  gcd(a,b%a);
}
ll lcm(ll a,ll b){
   return (a/gcd(a,b))*b;
}
ll add(ll a,ll b){
	a+=b;
	a+=mod;
	if(a>=mod) a%=mod;
	return a;
}
ll mul(ll a,ll b){return(a*b)%mod;}
#define maxn 200005
ll n,r,q;
ll a[maxn];
ll b[maxn];
ll in[maxn],out[maxn];
ll cnt[maxn];
vector<ll> g[maxn];
ll ti = 1;
void dfs(ll u){
    in[u] = ti;
    b[ti] = a[u];
    ti++;
    for(ll v : g[u]){
        dfs(v);
    }
    out[u] = ti-1;
}
bool in_t(ll v,ll u){
    return in[u]<=in[v]&&out[u]>=out[v];
}
map<pll,ll> pre;
vector<ll> w[maxn];
vector<pll> f;
void tc(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> r >> q;
    cin >> a[1];
    w[a[1]].pb(1);
    for(ll i = 2;i<=n;i++){
        ll x;
        cin >> x >> a[i];
        w[a[i]].pb(i);
        g[x].pb(i);
    }
    dfs(1);
    for(ll i = 1;i<=r;i++){
        fill(cnt,cnt+n+2,0);
        for(ll j : w[i]){
            cnt[in[j]]++;
            cnt[out[j]+1]--;
        }
        for(ll j = 1;j<ti;j++){
            cnt[j]+=cnt[j-1];
            pre[{i,b[j]}]+=cnt[j];
        }
    }
    while(q--){
        ll r1,r2;
        cin >> r1 >> r2;
        cout<<pre[{r1,r2}]<<endl;
    }
}
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
	//setIO("lol");
	int t; t = 1;
	while(t--){
		tc();
	}
	return 0;
}

Compilation message

regions.cpp: In function 'void setIO(std::string)':
regions.cpp:31:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  freopen((inoutname+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:32:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |      freopen((inoutname+".out").c_str(),"w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9672 KB Output is correct
2 Correct 6 ms 9672 KB Output is correct
3 Correct 7 ms 9672 KB Output is correct
4 Correct 10 ms 9800 KB Output is correct
5 Correct 13 ms 9808 KB Output is correct
6 Correct 60 ms 13572 KB Output is correct
7 Correct 67 ms 11200 KB Output is correct
8 Correct 86 ms 12356 KB Output is correct
9 Correct 230 ms 15840 KB Output is correct
10 Correct 522 ms 21440 KB Output is correct
11 Correct 503 ms 15476 KB Output is correct
12 Correct 1039 ms 24216 KB Output is correct
13 Correct 938 ms 18592 KB Output is correct
14 Correct 722 ms 14648 KB Output is correct
15 Correct 1249 ms 17900 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1977 ms 18640 KB Output is correct
2 Correct 2031 ms 18476 KB Output is correct
3 Correct 3373 ms 22352 KB Output is correct
4 Runtime error 2790 ms 131076 KB Execution killed with signal 9
5 Runtime error 3307 ms 131076 KB Execution killed with signal 9
6 Runtime error 2238 ms 131076 KB Execution killed with signal 9
7 Runtime error 2203 ms 131076 KB Execution killed with signal 9
8 Runtime error 2630 ms 131076 KB Execution killed with signal 9
9 Runtime error 3242 ms 131076 KB Execution killed with signal 9
10 Runtime error 2064 ms 131076 KB Execution killed with signal 9
11 Runtime error 2713 ms 131076 KB Execution killed with signal 9
12 Runtime error 3532 ms 131076 KB Execution killed with signal 9
13 Runtime error 3459 ms 131076 KB Execution killed with signal 9
14 Runtime error 3043 ms 131076 KB Execution killed with signal 9
15 Runtime error 2192 ms 131076 KB Execution killed with signal 9
16 Runtime error 2193 ms 131076 KB Execution killed with signal 9
17 Runtime error 2834 ms 131076 KB Execution killed with signal 9