oj.uz

답안 #446804

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446804 2021-07-23T10:22:21 Z BorisBarca Regions (IOI09_regions) C++14
10 / 100
 8000 ms 29536 KB 
/*
$$$$$$$\                      $$\           $$$$$$$\
$$  __$$\                     \__|          $$  __$$\
$$ |  $$ | $$$$$$\   $$$$$$\  $$\  $$$$$$$\ $$ |  $$ | $$$$$$\   $$$$$$\   $$$$$$$\ $$$$$$\
$$$$$$$\ |$$  __$$\ $$  __$$\ $$ |$$  _____|$$$$$$$\ | \____$$\ $$  __$$\ $$  _____|\____$$\
$$  __$$\ $$ /  $$ |$$ |  \__|$$ |\$$$$$$\  $$  __$$\  $$$$$$$ |$$ |  \__|$$ /      $$$$$$$ |
$$ |  $$ |$$ |  $$ |$$ |      $$ | \____$$\ $$ |  $$ |$$  __$$ |$$ |      $$ |     $$  __$$ |
$$$$$$$  |\$$$$$$  |$$ |      $$ |$$$$$$$  |$$$$$$$  |\$$$$$$$ |$$ |      \$$$$$$$\\$$$$$$$ |
\_______/  \______/ \__|      \__|\_______/ \_______/  \_______|\__|       \_______|\_______|
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define PB push_back
#define MP make_pair
#define INS insert
#define LB lower_bound
#define UB upper_bound
#define pii pair <int,int>
#define pll pair <long long, long long>
#define X first
#define Y second
#define _ << " " <<
#define sz(x) (int)x.size()
#define all(a) (a).begin(),(a).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (a); i > (b); --i)
#define FORA(i, x) for (auto &i : x)
#define REP(i, n) FOR(i, 0, n)
#define BITS(x) __builtin_popcount(x)
#define SQ(a) (a) * (a)
#define TRACE(x) cout << #x " = " << (x) << '\n';
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define umap unordered_map

typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef vector <pii> vpi;
typedef vector <ll> vll;
typedef vector <pll> vpl;
typedef vector <double> vd;
typedef vector <ld> vld;
typedef vector<string> vs;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
//find_by_order -> kti najmanji
//order_of_key -> koliko ima manjih od x
//((float) t)/CLOCKS_PER_SEC

const int MOD = 1e9 + 7;
const double PI = acos(-1);
const int INF = 1e9 + 10;
const ll INFL = 1e18 + 10;
const int ABC = 30;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dox[] = {-1, 1, 0, 0, -1, -1, 1, 1};
const int doy[] = {0, 0, -1, 1, -1, 1, -1, 1};

inline int sum(int a, int b){
	if (a + b < 0)
		return (a + b + MOD) % MOD;
	return (a + b) % MOD;
}

inline void add(int &a, int b){
	a = sum(a, b);
}

inline int mul(ll a, ll b){
	return ((a % MOD) * ((ll)b % MOD)) % MOD;
}

inline int sub(int a, int b){
	return (a - b + MOD) % MOD;
}

inline int fast_pot(ll pot, ll n){
	ll ret = 1;
	while (n){
		if (n & 1LL)
			ret = (ret * pot) % MOD;
		pot = (pot * pot) % MOD;
		n >>= 1LL;
	}
	return ret;
}

inline int divide(int a, int b){
	return mul(a, fast_pot(b, MOD - 2));
}

ll lcm(ll a, ll b){
	return abs(a * b) / __gcd(a, b);
}

inline int ccw(pii a, pii b, pii c) {
	return a.X * (b.Y - c.Y) + b.X * (c.Y - a.Y) + c.X * (a.Y - b.Y);
}


inline int CCW(pii A, pii B, pii C){
	double val = ccw(A, B, C);
	double eps = max(max(abs(A.X), abs(A.Y)), max(max(abs(B.X), abs(B.Y)), max(abs(C.X), abs(C.Y)))) / 1e9;
	if (val <= -eps)
		return -1;
	if (val >= eps)
		return 1;
	return 0;
}

void to_upper(string &x){
	REP(i, sz(x))
		x[i] = toupper(x[i]);
}

void to_lower(string &x){
	REP(i, sz(x))
		x[i] = tolower(x[i]);
}

string its(ll x){
	if (x == 0)
		return "0";
	string ret = "";
	while (x > 0){
		ret += (x % 10) + '0';
		x /= 10;
	}
	reverse(all(ret));
	return ret;
}

ll sti(string s){
	ll ret = 0;
	REP(i, sz(s)){
		ret *= 10;
		ret += (s[i] - '0');
	}
	return ret;
}

const int N = 2e5 + 10;
const int R = 25005;
const int LOG = 18;
const int OFF = 1 << LOG;

int n, r, q, st[N], en[N], idx, reg[N];
vi e[N], emp[R];

struct tournament{
	int t[2 * OFF], off;

	void init(int n){
		for (off = 1; off < n; off *= 2);
		memset(t, 0, sizeof t);
	}

	void send_prop(int node){
		for (auto c : {node * 2, node * 2 + 1})
			t[c] += t[node];
		t[node] = 0;
	}

	void update(int node, int a, int b, int lo, int hi, int  x){
		if (a > hi || b < lo)
			return;
		if (a >= lo && b <= hi){
			t[node] += x;
			return;
		}
		int mid = (a + b) / 2;
		send_prop(node);
		update(node * 2, a, mid, lo, hi, x);
		update(node * 2 + 1, mid + 1, b, lo, hi, x);
	}

	int query(int node, int a, int b, int lo, int hi){
		if (a > hi || b < lo)
			return 0;
		if (a >= lo && b <= hi)
			return t[node];
		send_prop(node);
		int mid = (a + b) / 2;
		return query(node * 2, a, mid, lo, hi) + query(node * 2 + 1, mid + 1, b, lo, hi);
	}

} T;

void dfs(int node, int dad){
	st[node] = idx++;
	en[node] = st[node];
	FORA(nxt, e[node]){
		if (nxt == dad)
			continue;
		dfs(nxt, node);
		en[node] = en[nxt];
	}
}

namespace regs{
	int cnt[R], sol[505][505];

	void dfs2(int node, int dad){
		REP(i, r)
			sol[i][reg[node]] += cnt[i];
		cnt[reg[node]]++;
		FORA(nxt, e[node]){
			if (nxt == dad)
				continue;
			dfs2(nxt, node);
		}
		cnt[reg[node]]--;
	}

	void solve(){
		dfs2(0, -1);
		while (q--){
			int a, b; cin >> a >> b;
			a--, b--;
			cout << sol[a][b] << endl;
			fflush(stdout);
		}
	}
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> r >> q;
	int h; cin >> h;
	h--;
	emp[h].PB(0);
	REP(i, n - 1){
		int s; cin >> s >> h;
		s--;
		h--;
		reg[i + 1] = h;
		e[s].PB(i + 1);
		emp[h].PB(i + 1);
	}

	if (r <= 500){
		regs::solve();
		return 0;
	}

	T.init(n);
	dfs(0, 0);
	while (q--){
		int r1, r2; cin >> r1 >> r2;
		r1--, r2--;

		FORA(el, emp[r1])
			T.update(1, 0, T.off - 1, st[el], en[el], 1);
		int sol = 0;
		FORA(el, emp[r2])
			sol += T.query(1, 0, T.off - 1, st[el], st[el]);

		cout << sol << endl;
		fflush(stdout);
		FORA(el, emp[r1])
			T.update(1, 0, T.off - 1, st[el], en[el], -1);
	}

	return 0;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 5576 KB Output isn't correct
2 Incorrect 4 ms 5576 KB Output isn't correct
3 Incorrect 6 ms 5576 KB Output isn't correct
4 Incorrect 7 ms 5576 KB Output isn't correct
5 Incorrect 12 ms 5704 KB Output isn't correct
6 Incorrect 28 ms 6088 KB Output isn't correct
7 Incorrect 27 ms 5960 KB Output isn't correct
8 Incorrect 19 ms 6088 KB Output isn't correct
9 Incorrect 72 ms 6736 KB Output isn't correct
10 Incorrect 48 ms 6832 KB Output isn't correct
11 Incorrect 103 ms 6728 KB Output isn't correct
12 Incorrect 186 ms 7496 KB Output isn't correct
13 Incorrect 197 ms 6856 KB Output isn't correct
14 Incorrect 119 ms 7156 KB Output isn't correct
15 Incorrect 206 ms 10168 KB Output isn't correct

Subtask #2
10.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 660 ms 9836 KB Output isn't correct
2 Incorrect 853 ms 8416 KB Output isn't correct
3 Incorrect 1097 ms 11824 KB Output isn't correct
4 Correct 1377 ms 9032 KB Output is correct
5 Correct 1267 ms 11028 KB Output is correct
6 Execution timed out 8083 ms 10192 KB Time limit exceeded
7 Execution timed out 8013 ms 11072 KB Time limit exceeded
8 Execution timed out 8066 ms 16836 KB Time limit exceeded
9 Execution timed out 8022 ms 16064 KB Time limit exceeded
10 Execution timed out 8057 ms 21972 KB Time limit exceeded
11 Execution timed out 8006 ms 15296 KB Time limit exceeded
12 Execution timed out 8096 ms 17088 KB Time limit exceeded
13 Execution timed out 8005 ms 17600 KB Time limit exceeded
14 Execution timed out 8080 ms 16992 KB Time limit exceeded
15 Execution timed out 8101 ms 22068 KB Time limit exceeded
16 Execution timed out 8005 ms 29536 KB Time limit exceeded
17 Execution timed out 8045 ms 27880 KB Time limit exceeded