oj.uz

답안 #545126

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
545126 2022-04-03T15:59:50 Z Bungmint Regions (IOI09_regions) C++17
3 / 100
 8000 ms 39896 KB 
//Copyright © 2022 Youngmin Park. All rights reserved.
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using vpi = vector<pii>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vpl = vector<pll>;
using ld = long double;
template <typename T, size_t SZ>
using ar = array<T, SZ>;

#define all(v) (v).begin(), (v).end()
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define REP(a) F0R(_, a)

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7; //998244353;
const ld PI = acos((ld)-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool ckmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p)
{
    return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v)
{
    os << '{';
    string sep;
    for (const T &x : v)
        os << sep << x, sep = ", ";
    return os << '}';
}
void dbg_out()
{
    cerr << endl;
}
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T)
{
    cerr << ' ' << H;
    dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

inline namespace RecursiveLambda{
	template <typename Fun>
	struct y_combinator_result{
		Fun fun_;
		template <typename T> 
		explicit y_combinator_result(T &&fun): fun_(forward<T>(fun)){}
		template <typename...Args>
		decltype(auto) operator()(Args &&...args){
			return fun_(ref(*this), forward<Args>(args)...);
		}
	};
	template <typename Fun>
	decltype(auto) y_combinator(Fun &&fun){
		return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
	}
};

void setIO(string s) // USACO
{
	#ifndef LOCAL
	    freopen((s + ".in").c_str(), "r", stdin);
	    freopen((s + ".out").c_str(), "w", stdout);
	#endif
}

const int N = 2e5, R = 25000;
const int B = 450;
vi adj[N];
int region[N], tin[N], tout[N];
vi reg[R];
int n, r, q, timer;
int co;
pll cache[B][R];
int id[R];
bool isBig[R];

void dfs(int u, int pu) {
	tin[u] = timer++;
	reg[region[u]].pb(u);
	for (auto &v : adj[u]) if (v != pu)	dfs(v, u);
	tout[u] = timer - 1;
}
ll calc(int i, int j) { // i - supervisor, j - employee
	int ptr = 0;
	ll res = 0;
	vi ts;
	F0R(x, sz(reg[j])) {
		int cur = tin[reg[j][x]];
		while (sz(ts) && tout[ts.back()] < cur) ts.pop_back();
		while (ptr < sz(reg[i]) && tout[reg[i][ptr]] < cur) ptr++;
		while (ptr < sz(reg[i]) && tin[reg[i][ptr]] <= cur) ts.pb(reg[i][ptr++]);
		res += sz(ts);
	}
	return res;
}

void solve()
{
	cin >> n >> r >> q;
	F0R(i, n) {
		if (i == 0) {
			cin >> region[i], region[i]--;
		}else{
			int p;
			cin >> p >> region[i];
			region[i]--, p--;
			adj[p].pb(i), adj[i].pb(p);
		}
	}
	dfs(0, -1);
	vi big;
	F0R(i, r) {
		if (sz(reg[i]) >= B) {
			big.pb(i);
			isBig[i] = 1;
		}
	}
	for (auto &rr : big) {
		id[rr] = co++;
		F0R(i, r) {
			if (i == rr) continue;
			cache[id[rr]][i] = {calc(rr, i), calc(i, rr)};
		}
	}
	REP(q) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		int res = {};
		if (isBig[u]) {
			res = cache[id[u]][v].fi;
		}else if (isBig[v]) {
			res = cache[id[v]][u].se;
		}else{
			res = calc(u, v);
		}
		cout << res << endl;
	}
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int testcase=1;
    // cin >> testcase;
    while (testcase--)
    {
        solve();
    }
}

Compilation message

regions.cpp: In function 'void setIO(std::string)':
regions.cpp:94:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |      freopen((s + ".in").c_str(), "r", stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:95:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |      freopen((s + ".out").c_str(), "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5584 KB Output isn't correct
2 Incorrect 3 ms 5524 KB Output isn't correct
3 Incorrect 4 ms 5504 KB Output isn't correct
4 Incorrect 7 ms 5584 KB Output isn't correct
5 Incorrect 9 ms 5572 KB Output isn't correct
6 Correct 19 ms 5584 KB Output is correct
7 Incorrect 29 ms 5584 KB Output isn't correct
8 Incorrect 32 ms 5712 KB Output isn't correct
9 Correct 53 ms 6096 KB Output is correct
10 Incorrect 71 ms 6096 KB Output isn't correct
11 Incorrect 96 ms 6352 KB Output isn't correct
12 Incorrect 88 ms 6764 KB Output isn't correct
13 Incorrect 158 ms 6864 KB Output isn't correct
14 Incorrect 202 ms 7144 KB Output isn't correct
15 Correct 278 ms 9424 KB Output is correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1090 ms 10120 KB Output isn't correct
2 Incorrect 1074 ms 9972 KB Output isn't correct
3 Incorrect 1638 ms 11748 KB Output isn't correct
4 Incorrect 253 ms 7212 KB Output isn't correct
5 Incorrect 317 ms 8656 KB Output isn't correct
6 Incorrect 1985 ms 15432 KB Output isn't correct
7 Incorrect 1327 ms 11796 KB Output isn't correct
8 Incorrect 4177 ms 30060 KB Output isn't correct
9 Incorrect 1732 ms 14140 KB Output isn't correct
10 Incorrect 6056 ms 39896 KB Output isn't correct
11 Incorrect 2587 ms 16380 KB Output isn't correct
12 Incorrect 4201 ms 15884 KB Output isn't correct
13 Incorrect 4733 ms 16776 KB Output isn't correct
14 Execution timed out 8013 ms 23236 KB Time limit exceeded
15 Execution timed out 8018 ms 19848 KB Time limit exceeded
16 Incorrect 6137 ms 25412 KB Output isn't correct
17 Execution timed out 8023 ms 30768 KB Time limit exceeded