oj.uz

답안 #446807

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446807 2021-07-23T10:39:33 Z BorisBarca Regions (IOI09_regions) C++14
50 / 100
 8000 ms 31172 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];
map <int, int> answ[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);
	reg[0] = h;
	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, -1);
	while (q--){
		int r1, r2; cin >> r1 >> r2;
		r1--, r2--;

		if (answ[r1].count(r2)){
			cout << answ[r1][r2] << endl;
			fflush(stdout);
			continue;
		}

		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;
		answ[r1][r2] = sol;
		fflush(stdout);
		FORA(el, emp[r1])
			T.update(1, 0, T.off - 1, st[el], en[el], -1);
	}

	return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6728 KB Output is correct
2 Correct 5 ms 6728 KB Output is correct
3 Correct 7 ms 6728 KB Output is correct
4 Correct 8 ms 6776 KB Output is correct
5 Correct 11 ms 6792 KB Output is correct
6 Correct 29 ms 7368 KB Output is correct
7 Correct 34 ms 7112 KB Output is correct
8 Correct 36 ms 7240 KB Output is correct
9 Correct 54 ms 7880 KB Output is correct
10 Correct 108 ms 8024 KB Output is correct
11 Correct 101 ms 7880 KB Output is correct
12 Correct 75 ms 8776 KB Output is correct
13 Correct 148 ms 8108 KB Output is correct
14 Correct 84 ms 8336 KB Output is correct
15 Correct 213 ms 11380 KB Output is correct

Subtask #2
35.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 646 ms 10940 KB Output is correct
2 Correct 754 ms 9620 KB Output is correct
3 Correct 1295 ms 13056 KB Output is correct
4 Correct 1308 ms 11556 KB Output is correct
5 Correct 1303 ms 13892 KB Output is correct
6 Correct 1738 ms 13128 KB Output is correct
7 Correct 1625 ms 13368 KB Output is correct
8 Execution timed out 8082 ms 20656 KB Time limit exceeded
9 Execution timed out 8007 ms 20220 KB Time limit exceeded
10 Execution timed out 8037 ms 24828 KB Time limit exceeded
11 Execution timed out 8013 ms 19044 KB Time limit exceeded
12 Execution timed out 8071 ms 18876 KB Time limit exceeded
13 Execution timed out 8058 ms 19248 KB Time limit exceeded
14 Execution timed out 8087 ms 18720 KB Time limit exceeded
15 Execution timed out 8009 ms 23652 KB Time limit exceeded
16 Execution timed out 8029 ms 31172 KB Time limit exceeded
17 Execution timed out 8028 ms 29744 KB Time limit exceeded