oj.uz

답안 #430901

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
430901 2021-06-17T07:50:15 Z amunduzbaev Regions (IOI09_regions) C++14
45 / 100
 8000 ms 35716 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;
			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 9 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 24 ms 10696 KB Output is correct
7 Correct 32 ms 10312 KB Output is correct
8 Correct 38 ms 10568 KB Output is correct
9 Correct 55 ms 11324 KB Output is correct
10 Correct 84 ms 11716 KB Output is correct
11 Correct 112 ms 11404 KB Output is correct
12 Correct 137 ms 12544 KB Output is correct
13 Correct 139 ms 11592 KB Output is correct
14 Correct 161 ms 11584 KB Output is correct
15 Correct 189 ms 14676 KB Output is correct

Subtask #2
30.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 762 ms 14192 KB Output is correct
2 Correct 734 ms 12960 KB Output is correct
3 Correct 1174 ms 16352 KB Output is correct
4 Correct 1163 ms 12252 KB Output is correct
5 Correct 1203 ms 14360 KB Output is correct
6 Correct 6924 ms 14164 KB Output is correct
7 Execution timed out 8010 ms 16448 KB Time limit exceeded
8 Execution timed out 8067 ms 21608 KB Time limit exceeded
9 Execution timed out 8038 ms 24768 KB Time limit exceeded
10 Execution timed out 8100 ms 29436 KB Time limit exceeded
11 Execution timed out 8012 ms 25316 KB Time limit exceeded
12 Execution timed out 8057 ms 26432 KB Time limit exceeded
13 Execution timed out 8028 ms 26688 KB Time limit exceeded
14 Execution timed out 8007 ms 26436 KB Time limit exceeded
15 Execution timed out 8080 ms 30348 KB Time limit exceeded
16 Execution timed out 8085 ms 35716 KB Time limit exceeded
17 Execution timed out 8006 ms 34900 KB Time limit exceeded