oj.uz

Submission #430897

# Submission time Handle Problem Language Result Execution time Memory
430897 2021-06-17T07:45:40 Z amunduzbaev Regions (IOI09_regions) C++14
30 / 100
 8000 ms 35744 KB 
/* made by amunduzbaev */
 
#include "bits/stdc++.h"
 
using namespace std;
 
//~ #include <ext/pb_ds/assoc_container.hpp>
//~ #include <ext/pb_ds/tree_policy.hpp>
//~ using namespace __gnu_pbds;
//~ template<class T> using oset = tree<T, 
//~ null_type, less_equal<T>, rb_tree_tag, 
//~ tree_order_statistics_node_update>;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vv vector
#define mem(arr, v) memset(arr, v, sizeof arr)
#define int long long
#define degub(x) cout<<#x<<" : "<<x<<"\n"
#define GG cout<<"here"<<endl;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef vector<int> vii;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T> bool umax(T& a, const T& b) { return a < b ? a = b, true : false; }
template<int sz> using tut = array<int, sz>;
void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);  
	freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
 
const int N = 2e5+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
 
#define MULTI 0
int n, m, k, t, q, ans, res, a[N];
int tin[N], tout[N];
vii edges[N], tt[N];

void dfs(int u, int p = -1){
	tin[u] = t++;
	for(auto x : edges[u]){
		if(x == p) continue;
		dfs(x, u);
	} tout[u] = t - 1;
}

int tree[4*N];

void add(int l, int r, int v, int lx = 0, int rx = n, int x = 1){
	if(lx > r || rx < l) return;
	if(lx >= l && rx <= r) { tree[x] += v; return; }
	int m = (lx + rx)>>1;
	add(l, r, v, lx, m, x<<1), add(l, r, v, m+1, rx, x<<1|1);
}

int get(int i, int lx = 0, int rx = n, int x = 1){
	if(lx == rx) return tree[x];
	int m = (lx + rx)>>1;
	if(i <= m) return tree[x] + get(i, lx, m, x<<1);
	else return tree[x] + get(i, m+1, rx, x<<1|1);
}

void solve(int t_case){
	cin>>n>>m>>q;
	cin>>a[1];
	for(int i=2;i<=n;i++){
		int x; cin>>x>>a[i], edges[x].pb(i); 
	} dfs(1);
	for(int i=1;i<=n;i++) tt[a[i]].pb(i);
	
	
	for(int i=0;i<q;i++){
		int a, b; cin>>a>>b;
		for(auto x : tt[a]) add(tin[x], tout[x], 1);
		res = 0;
		for(auto x : tt[b]) res += get(tin[x]);
		for(auto x : tt[a]) add(tin[x], tout[x], -1);
		cout<<res<<endl;
	}
}

signed main(){
	NeedForSpeed
	if(MULTI){
		int t; cin>>t;
		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
	} else solve(1);
	return 0;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9672 KB Output is correct
2 Correct 7 ms 9672 KB Output is correct
3 Correct 9 ms 9672 KB Output is correct
4 Correct 10 ms 9740 KB Output is correct
5 Correct 16 ms 9672 KB Output is correct
6 Correct 25 ms 9800 KB Output is correct
7 Correct 44 ms 9800 KB Output is correct
8 Correct 38 ms 9912 KB Output is correct
9 Correct 67 ms 10440 KB Output is correct
10 Correct 162 ms 10568 KB Output is correct
11 Correct 348 ms 10896 KB Output is correct
12 Correct 403 ms 11776 KB Output is correct
13 Correct 593 ms 11532 KB Output is correct
14 Correct 1244 ms 12240 KB Output is correct
15 Correct 1897 ms 15388 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8016 ms 17376 KB Time limit exceeded
2 Execution timed out 8047 ms 16344 KB Time limit exceeded
3 Execution timed out 8005 ms 19264 KB Time limit exceeded
4 Correct 1026 ms 12244 KB Output is correct
5 Correct 1211 ms 14400 KB Output is correct
6 Correct 7504 ms 14144 KB Output is correct
7 Execution timed out 8066 ms 16392 KB Time limit exceeded
8 Execution timed out 8083 ms 21620 KB Time limit exceeded
9 Execution timed out 8039 ms 24812 KB Time limit exceeded
10 Execution timed out 8087 ms 29452 KB Time limit exceeded
11 Execution timed out 8054 ms 25280 KB Time limit exceeded
12 Execution timed out 8052 ms 26324 KB Time limit exceeded
13 Execution timed out 8067 ms 26652 KB Time limit exceeded
14 Execution timed out 8074 ms 26428 KB Time limit exceeded
15 Execution timed out 8042 ms 30380 KB Time limit exceeded
16 Execution timed out 8032 ms 35744 KB Time limit exceeded
17 Execution timed out 8077 ms 34880 KB Time limit exceeded