oj.uz

답안 #446562

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446562 2021-07-22T12:27:59 Z BorisBarca Regions (IOI09_regions) C++14
25 / 100
 8000 ms 28764 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 LOG = 18;
const int OFF = 1 << LOG;

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

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];
	}
}

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--;
		e[s].PB(i + 1);
		emp[h].PB(i + 1);
	}

	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
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7624 KB Output is correct
2 Correct 5 ms 7624 KB Output is correct
3 Correct 6 ms 7624 KB Output is correct
4 Correct 10 ms 7624 KB Output is correct
5 Correct 17 ms 7624 KB Output is correct
6 Correct 34 ms 7624 KB Output is correct
7 Correct 49 ms 7624 KB Output is correct
8 Correct 60 ms 7752 KB Output is correct
9 Correct 107 ms 8136 KB Output is correct
10 Correct 204 ms 8008 KB Output is correct
11 Correct 394 ms 8300 KB Output is correct
12 Correct 444 ms 8776 KB Output is correct
13 Correct 634 ms 8324 KB Output is correct
14 Correct 1422 ms 8904 KB Output is correct
15 Correct 2023 ms 11976 KB Output is correct

Subtask #2
10.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8067 ms 11716 KB Time limit exceeded
2 Execution timed out 8077 ms 10312 KB Time limit exceeded
3 Execution timed out 8012 ms 13704 KB Time limit exceeded
4 Correct 1235 ms 8904 KB Output is correct
5 Correct 1290 ms 10816 KB Output is correct
6 Execution timed out 8079 ms 10048 KB Time limit exceeded
7 Execution timed out 8029 ms 10816 KB Time limit exceeded
8 Execution timed out 8079 ms 16452 KB Time limit exceeded
9 Execution timed out 8032 ms 15624 KB Time limit exceeded
10 Execution timed out 8079 ms 21248 KB Time limit exceeded
11 Execution timed out 8018 ms 14504 KB Time limit exceeded
12 Execution timed out 8102 ms 16288 KB Time limit exceeded
13 Execution timed out 8080 ms 16804 KB Time limit exceeded
14 Execution timed out 8010 ms 16196 KB Time limit exceeded
15 Execution timed out 8018 ms 21312 KB Time limit exceeded
16 Execution timed out 8063 ms 28764 KB Time limit exceeded
17 Execution timed out 8077 ms 27088 KB Time limit exceeded