oj.uz

답안 #430906

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
430906 2021-06-17T07:52:37 Z amunduzbaev Regions (IOI09_regions) C++14
40 / 100
 8000 ms 67152 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);
			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 10 ms 9800 KB Output is correct
5 Correct 9 ms 9928 KB Output is correct
6 Correct 23 ms 10716 KB Output is correct
7 Correct 20 ms 10312 KB Output is correct
8 Correct 37 ms 10568 KB Output is correct
9 Correct 56 ms 11336 KB Output is correct
10 Correct 99 ms 11760 KB Output is correct
11 Correct 65 ms 11400 KB Output is correct
12 Correct 120 ms 12488 KB Output is correct
13 Correct 146 ms 11716 KB Output is correct
14 Correct 118 ms 11464 KB Output is correct
15 Correct 191 ms 14712 KB Output is correct

Subtask #2
25.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 702 ms 14252 KB Output is correct
2 Correct 835 ms 12992 KB Output is correct
3 Correct 972 ms 16320 KB Output is correct
4 Correct 1020 ms 12244 KB Output is correct
5 Correct 1084 ms 14408 KB Output is correct
6 Runtime error 36 ms 26568 KB Execution killed with signal 6
7 Execution timed out 8084 ms 16456 KB Time limit exceeded
8 Runtime error 62 ms 43408 KB Execution killed with signal 6
9 Execution timed out 8025 ms 24768 KB Time limit exceeded
10 Execution timed out 8016 ms 29444 KB Time limit exceeded
11 Execution timed out 8080 ms 25280 KB Time limit exceeded
12 Runtime error 122 ms 50128 KB Execution killed with signal 6
13 Runtime error 117 ms 51288 KB Execution killed with signal 6
14 Runtime error 126 ms 50128 KB Execution killed with signal 6
15 Runtime error 107 ms 59196 KB Execution killed with signal 6
16 Runtime error 114 ms 67152 KB Execution killed with signal 6
17 Runtime error 107 ms 64808 KB Execution killed with signal 6