oj.uz

답안 #430907

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
430907 2021-06-17T07:53:37 Z amunduzbaev Regions (IOI09_regions) C++14
45 / 100
 8000 ms 64760 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 cnt[N], col[505][505];
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 dfs1(int u, int p = -1){
	for(int i=1;i<=m;i++) col[i][a[u]] += cnt[i];
	cnt[a[u]]++;
	for(auto x : edges[u]){
		if(x == p) continue;
		dfs1(x, u);
	} cnt[a[u]]--;
}

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); 
	} 
	
	if(m <= 500){
		dfs1(1);
		for(int i=0;i<q;i++){
			int a, b; cin>>a>>b;
			cout<<col[a][b]<<endl;
		}
	} else {
		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;
			assert(sz(tt[a]) <= 500 && sz(tt[b]) <= 500);
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9672 KB Output is correct
2 Correct 6 ms 9672 KB Output is correct
3 Correct 8 ms 9800 KB Output is correct
4 Correct 11 ms 9800 KB Output is correct
5 Correct 12 ms 9928 KB Output is correct
6 Correct 23 ms 10692 KB Output is correct
7 Correct 33 ms 10312 KB Output is correct
8 Correct 21 ms 10568 KB Output is correct
9 Correct 55 ms 11336 KB Output is correct
10 Correct 52 ms 11720 KB Output is correct
11 Correct 100 ms 11336 KB Output is correct
12 Correct 115 ms 12488 KB Output is correct
13 Correct 95 ms 11692 KB Output is correct
14 Correct 85 ms 11552 KB Output is correct
15 Correct 178 ms 14656 KB Output is correct

Subtask #2
30.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 705 ms 14212 KB Output is correct
2 Correct 758 ms 12976 KB Output is correct
3 Correct 1117 ms 16320 KB Output is correct
4 Correct 992 ms 12248 KB Output is correct
5 Correct 1127 ms 14364 KB Output is correct
6 Correct 7118 ms 14132 KB Output is correct
7 Execution timed out 8077 ms 16360 KB Time limit exceeded
8 Execution timed out 8086 ms 21680 KB Time limit exceeded
9 Execution timed out 8087 ms 24768 KB Time limit exceeded
10 Execution timed out 8004 ms 29376 KB Time limit exceeded
11 Execution timed out 8023 ms 25280 KB Time limit exceeded
12 Runtime error 113 ms 45140 KB Execution killed with signal 6
13 Runtime error 109 ms 45680 KB Execution killed with signal 6
14 Runtime error 123 ms 49892 KB Execution killed with signal 6
15 Runtime error 121 ms 59212 KB Execution killed with signal 6
16 Runtime error 106 ms 64064 KB Execution killed with signal 6
17 Runtime error 109 ms 64760 KB Execution killed with signal 6