oj.uz

답안 #431915

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
431915 2021-06-17T17:12:22 Z amunduzbaev Regions (IOI09_regions) C++14
0 / 100
 3901 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(!id[a[u]]){
		for(auto x : cnt) 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 }
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 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 13 ms 9712 KB Output isn't correct
5 Incorrect 16 ms 9748 KB Output isn't correct
6 Incorrect 27 ms 10012 KB Output isn't correct
7 Incorrect 34 ms 9800 KB Output isn't correct
8 Incorrect 31 ms 9948 KB Output isn't correct
9 Incorrect 57 ms 11068 KB Output isn't correct
10 Incorrect 85 ms 10440 KB Output isn't correct
11 Incorrect 122 ms 11028 KB Output isn't correct
12 Incorrect 159 ms 12128 KB Output isn't correct
13 Incorrect 172 ms 11484 KB Output isn't correct
14 Incorrect 251 ms 12232 KB Output isn't correct
15 Incorrect 222 ms 20560 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1260 ms 18928 KB Output isn't correct
2 Incorrect 1119 ms 16304 KB Output isn't correct
3 Incorrect 1895 ms 23948 KB Output isn't correct
4 Incorrect 271 ms 12384 KB Output isn't correct
5 Incorrect 388 ms 17368 KB Output isn't correct
6 Incorrect 1246 ms 14404 KB Output isn't correct
7 Incorrect 1379 ms 15808 KB Output isn't correct
8 Incorrect 1782 ms 30064 KB Output isn't correct
9 Incorrect 2377 ms 25416 KB Output isn't correct
10 Incorrect 3240 ms 39548 KB Output isn't correct
11 Incorrect 3901 ms 24112 KB Output isn't correct
12 Incorrect 1275 ms 71100 KB Output isn't correct
13 Incorrect 1743 ms 72672 KB Output isn't correct
14 Incorrect 2316 ms 82916 KB Output isn't correct
15 Incorrect 2507 ms 118928 KB Output isn't correct
16 Runtime error 139 ms 131076 KB Execution killed with signal 9
17 Incorrect 2331 ms 118032 KB Output isn't correct