답안 #431912

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
431912 2021-06-17T17:06:27 Z amunduzbaev Regions (IOI09_regions) C++14
0 / 100
4235 ms 131076 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);
const int B = 500;
 
#define MULTI 0
int n, m, k, t, q, ans, res, a[N];
int heavy[N], last[N], id[N], cnt[N];
int bs[N / B + 10][N];
int sb[N][N / B + 10];
vii edges[N];
vpii cmp[N];

//~ BIG_SMALL BIG_BIG
int cur;
void bsdfs(int u, int p = -1, int cnt = 0){
	if(id[a[u]] == cur) cnt++;
	bs[cur][a[u]] += cnt;
	for(auto x : edges[u]) bsdfs(x, u, cnt);
}

//~ SMALL_BIG
map<int, int> sbdfs(int u, int p = -1){
	map<int, int> cnt;
	if(id[a[u]]) cnt[id[a[u]]]++;
	for(auto x : edges[u]) {
		map<int, int> tmp = sbdfs(x, u);
		if(sz(tmp) > sz(cnt)) swap(cnt, tmp);
		for(auto x : tmp) cnt[x.ff] += x.ss;
	}
	
	if(!heavy[a[u]]){
		for(auto x : cnt) assert(x.ff <= N / B + 10), sb[a[u]][x.ff] += x.ss;
	} return cnt;
}

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

bool par(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); }

void solve(int t_case){
	cin>>n>>m>>q;
	cin>>a[1];
	for(int i=2;i<=n;i++){
		int p; cin>>p>>a[i];
		edges[p].pb(i);
	}
	
	for(int i=1;i<=n;i++) cnt[a[i]]++;
	int last = 1;
	for(int i=1;i<=m;i++){
		if(cnt[i] > B) id[i] = last++;
	}
	
	for(int i=1;i<last;i++) cur = i, bsdfs(1);
	sbdfs(1), dfs(1);
	for(int i=1;i<=n;i++) cmp[a[i]].pb({tin[i], tout[i]});
	for(int i=1;i<=m;i++) sort(all(cmp[i]));

	for(int i=1;i<=q;i++){
		int x, b; cin>>x>>b;
		if(id[a[x]]) cout<<bs[id[a[x]]][a[b]]<<endl;
		else if(id[a[b]]) cout<<sb[a[x]][id[a[b]]]<<endl;
		else { res = 0; 
			//~ SMALL_SMALL
			for(auto tt : cmp[a[x]]){
				int lx = lb(all(cmp[a[b]]), mp(tt.ff, -1ll)) - cmp[a[b]].begin();
				int rx = ub(all(cmp[a[b]]), mp(tt.ss, tt.ss)) - cmp[a[b]].begin();
				res += rx - lx;
			} 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 }
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9672 KB Output isn't correct
2 Incorrect 7 ms 9672 KB Output isn't correct
3 Incorrect 9 ms 9672 KB Output isn't correct
4 Incorrect 11 ms 9672 KB Output isn't correct
5 Incorrect 13 ms 9800 KB Output isn't correct
6 Incorrect 24 ms 9976 KB Output isn't correct
7 Incorrect 34 ms 9800 KB Output isn't correct
8 Incorrect 39 ms 9928 KB Output isn't correct
9 Incorrect 55 ms 11080 KB Output isn't correct
10 Incorrect 56 ms 10440 KB Output isn't correct
11 Incorrect 134 ms 11032 KB Output isn't correct
12 Incorrect 152 ms 12180 KB Output isn't correct
13 Incorrect 165 ms 11492 KB Output isn't correct
14 Incorrect 284 ms 12232 KB Output isn't correct
15 Incorrect 306 ms 20560 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1144 ms 18952 KB Output isn't correct
2 Incorrect 1160 ms 16328 KB Output isn't correct
3 Incorrect 1888 ms 24000 KB Output isn't correct
4 Incorrect 287 ms 12384 KB Output isn't correct
5 Incorrect 385 ms 17328 KB Output isn't correct
6 Incorrect 1343 ms 14384 KB Output isn't correct
7 Incorrect 1264 ms 15808 KB Output isn't correct
8 Incorrect 2139 ms 30024 KB Output isn't correct
9 Incorrect 2435 ms 25420 KB Output isn't correct
10 Incorrect 4235 ms 39544 KB Output isn't correct
11 Incorrect 4166 ms 24112 KB Output isn't correct
12 Incorrect 1275 ms 71100 KB Output isn't correct
13 Incorrect 1703 ms 72676 KB Output isn't correct
14 Incorrect 2420 ms 82984 KB Output isn't correct
15 Incorrect 2528 ms 119096 KB Output isn't correct
16 Runtime error 137 ms 131076 KB Execution killed with signal 9
17 Incorrect 2503 ms 118004 KB Output isn't correct