oj.uz

Submission #490677

# Submission time Handle Problem Language Result Execution time Memory
490677 2021-11-28T14:46:06 Z Karliver Regions (IOI09_regions) C++17
35 / 100
 5459 ms 46348 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]);
			}
		}
		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 4 ms 6728 KB Output is correct
3 Correct 5 ms 6728 KB Output is correct
4 Correct 8 ms 6728 KB Output is correct
5 Correct 12 ms 6728 KB Output is correct
6 Correct 20 ms 6728 KB Output is correct
7 Correct 28 ms 6728 KB Output is correct
8 Correct 37 ms 6856 KB Output is correct
9 Correct 47 ms 7112 KB Output is correct
10 Correct 82 ms 7240 KB Output is correct
11 Correct 147 ms 7496 KB Output is correct
12 Correct 161 ms 7880 KB Output is correct
13 Correct 227 ms 7632 KB Output is correct
14 Correct 286 ms 8144 KB Output is correct
15 Correct 365 ms 9928 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 21568 KB Execution killed with signal 11
2 Runtime error 32 ms 19556 KB Execution killed with signal 11
3 Runtime error 35 ms 24512 KB Execution killed with signal 11
4 Correct 286 ms 8160 KB Output is correct
5 Correct 464 ms 9416 KB Output is correct
6 Runtime error 28 ms 18624 KB Execution killed with signal 11
7 Runtime error 35 ms 20360 KB Execution killed with signal 11
8 Runtime error 43 ms 28184 KB Execution killed with signal 11
9 Correct 3358 ms 14704 KB Output is correct
10 Runtime error 72 ms 37280 KB Execution killed with signal 11
11 Correct 5459 ms 14344 KB Output is correct
12 Runtime error 92 ms 32832 KB Execution killed with signal 11
13 Runtime error 85 ms 32672 KB Execution killed with signal 11
14 Runtime error 94 ms 32304 KB Execution killed with signal 11
15 Runtime error 91 ms 38916 KB Execution killed with signal 11
16 Runtime error 98 ms 46348 KB Execution killed with signal 11
17 Runtime error 88 ms 44648 KB Execution killed with signal 11