oj.uz

Submission #490678

# Submission time Handle Problem Language Result Execution time Memory
490678 2021-11-28T14:48:12 Z Karliver Regions (IOI09_regions) C++17
60 / 100
 8000 ms 26576 KB 
	
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()

using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;

const int INF = 1e9 + 1;
const int MX = 2e5 + 10;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
    return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
    return (x > y ? x = y, 1 : 0);
}
struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTree(int _n) {
        this->n = _n;
        bit.assign(n, 0);
    }

    FenwickTree(vector<int> a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }

    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};
int N, R, Q;
bool ishe[MX];
V<int> heavy;
V<int> g[MX];
int tin[MX], tout[MX];
int T = 1;
void dfs(int v) {
	tin[v] = T++;
	for(auto c : g[v])
		dfs(c);
	tout[v] = T - 1;
}
V<int> rg[25002];
V<ll> FT[25002];
V<ll> TF[25002];
const int B = 420;
void solve() {

	cin >> N >> R >> Q;

	int a, b;
	cin >> a;
	rg[a].push_back(1);	

	for(int i = 2;i <= N;++i) {
		
		cin >> a >> b;
		g[a].push_back(i);
		rg[b].push_back(i);
	}
	dfs(1);
	FenwickTree F(N + 1);

	
	for(int i = 1;i <= R;++i) {
		if(sz(rg[i]) < B)
			continue;
		ishe[i] = 1;
		for(auto c : rg[i])
			F.add(tin[c], 1);
		TF[i].resize(R + 1);
		for(int j = 1;j <= R;++j) {
			for(auto x : rg[j]) {
				TF[i][j] += F.sum(tin[x], tout[x]);
			}
		}
		FT[i].resize(R + 1);
		for(auto c : rg[i])
			F.add(tin[c], -1);
		for(int j = 1;j <= R;++j) {
			if(j == i)continue;
			for(auto x : rg[j])
				F.add(tin[x], 1);

			for(auto c : rg[i])
				FT[i][j] += F.sum(tin[c], tout[c]);

			for(auto x : rg[j])
				F.add(tin[x], -1);
		}
	}

	while(Q--) {
		int r1, r2;
		cin >> r1 >> r2;

		if(ishe[r2]) {
			cout << TF[r2][r1] << endl;
			continue;
		}
		if(ishe[r1]) {
			cout << FT[r1][r2] << endl;
			continue;
		}
		for(auto c : rg[r2])
			F.add(tin[c], 1);
		int ret = 0;
		for(auto c : rg[r1])
			ret += F.sum(tin[c], tout[c]);

		cout << ret << endl;
		for(auto c : rg[r2])
			F.add(tin[c], -1);
	}




	



}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        //cout << "Case #" << p + 1 << ": ";
        solve();
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6728 KB Output is correct
2 Correct 5 ms 6728 KB Output is correct
3 Correct 5 ms 6728 KB Output is correct
4 Correct 9 ms 6728 KB Output is correct
5 Correct 13 ms 6728 KB Output is correct
6 Correct 21 ms 6728 KB Output is correct
7 Correct 37 ms 6856 KB Output is correct
8 Correct 47 ms 6856 KB Output is correct
9 Correct 63 ms 7192 KB Output is correct
10 Correct 118 ms 7240 KB Output is correct
11 Correct 124 ms 7496 KB Output is correct
12 Correct 190 ms 7880 KB Output is correct
13 Correct 219 ms 7604 KB Output is correct
14 Correct 299 ms 8136 KB Output is correct
15 Correct 425 ms 9928 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1609 ms 10816 KB Output is correct
2 Correct 1946 ms 9792 KB Output is correct
3 Correct 3515 ms 12312 KB Output is correct
4 Correct 418 ms 8164 KB Output is correct
5 Correct 509 ms 9348 KB Output is correct
6 Correct 6875 ms 15752 KB Output is correct
7 Correct 4814 ms 13600 KB Output is correct
8 Execution timed out 8021 ms 22828 KB Time limit exceeded
9 Correct 3433 ms 14656 KB Output is correct
10 Execution timed out 8061 ms 26576 KB Time limit exceeded
11 Correct 5965 ms 14280 KB Output is correct
12 Execution timed out 8064 ms 16304 KB Time limit exceeded
13 Execution timed out 8082 ms 16312 KB Time limit exceeded
14 Execution timed out 8095 ms 16724 KB Time limit exceeded
15 Execution timed out 8096 ms 19392 KB Time limit exceeded
16 Execution timed out 8076 ms 23140 KB Time limit exceeded
17 Execution timed out 8086 ms 23180 KB Time limit exceeded