oj.uz

답안 #363485

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
363485 2021-02-06T08:38:53 Z Return_0 동기화 (JOI13_synchronization) C++17
100 / 100
 406 ms 28652 KB 
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef int ll;
typedef long double ld;
typedef pair <ll, ll> pll;

#ifdef SINA
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1);
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< x << endl, 0
#define cl const ll
#define fr first
#define sc second
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()

cl inf = sizeof(ll) == 4 ? (1e9 + 10) : (3e18), mod = 1e9 + 7, MOD = 998244353;

template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
	return out << '(' << a.first << ", " << a.second << ')';    }
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
	if(a.empty())return out<<"[]";out<< '[' << a[0]; for (int i = 0; ++i < (int)(a.size());) out<< ", " << a[i];out<< ']';  }
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

cl N = 2e5 + 7;

ll dp [N], up [N], tin [N], rtin [N], tout [N], T, n, m, q;
vector <ll> adj [N];
bool mark [N];
pll e [N];

void dfs (cl &v = 1, cl &pr = 1) {
	tin[v] = ++T;
	rtin[T] = v;
	for (auto &u : adj[v]) if (u ^ pr)	dfs(u, v);
	tout[v] = T;
}

struct seg {
	ll mx, l, r;
	seg *lt, *rt;
	inline seg (cl &L = 1, cl &R = N - 2) : mx(0), l(L), r(R) {}

	void build () {
		if (l == r) {
			mx = tout[rtin[l]];
			return;
		}
		lt = new seg (l, mid);
		rt = new seg (mid + 1, r);
		lt->build();
		rt->build();
		mx = max(lt->mx, rt->mx);
	}

	void upd (cl &pos, cl &x) {
		if (l == r)	{
			mx = x;
			return;
		}
		if (pos <= mid)	lt->upd(pos, x);
		else rt->upd(pos, x);
		mx = max(lt->mx, rt->mx);
	}

	ll ask (cl &qr, cl &x) {
		if (mx < x)	return 1;
		if (l == r)	return l;
		if (r <= qr) {
			if (rt->mx >= x)	return rt->ask(qr, x);
			return lt->ask(qr, x);
		}
		ll y = 1;
		if (rt->mx >= x && rt->l <= qr)	y = rt->ask(qr, x);
		if (y == 1)	y = lt->ask(qr, x);
		return y;
	}
} mytree;

ll ask (cl &qr, cl &x) {
	ll ret = mytree.ask(qr, x);
	ret = rtin[ret];
	return ret;
}

int main ()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	fill(dp, dp + N, 1);

	cin>> n >> m >> q;
	for (ll i = 1, v, u; i < n; i++) {
		cin>> v >> u;
		e[i] = {v, u};
		adj[v].push_back(u);
		adj[u].push_back(v);
	}

	dfs();
	mytree.r = n;	mytree.build();

	for (ll i = 0, x; i < m; i++) {
		cin>> x;
		if (tin[e[x].fr] > tin[e[x].sc])	swap(e[x].fr, e[x].sc);
		if (!mark[x])	{
			dp[ask(tin[e[x].fr], tout[e[x].fr])] += dp[e[x].sc] - up[e[x].sc];
			mytree.upd(tin[e[x].sc], 0);
		} else {
			dp[e[x].sc] = up[e[x].sc] = dp[ask(tin[e[x].sc], tout[e[x].sc])];
			mytree.upd(tin[e[x].sc], tout[e[x].sc]);
		}
		mark[x] ^= 1;
	}

	for (ll v; q--;) {
		cin>> v;
		cout<< dp[ask(tin[v], tout[v])] << '\n';
	}

	return 0;
}
/*

*/

Compilation message

synchronization.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<_Tp>&)':
synchronization.cpp:44:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   44 |  if(a.empty())return out<<"[]";out<< '[' << a[0]; for (int i = 0; ++i < (int)(a.size());) out<< ", " << a[i];out<< ']';  }
      |  ^~
synchronization.cpp:44:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   44 |  if(a.empty())return out<<"[]";out<< '[' << a[0]; for (int i = 0; ++i < (int)(a.size());) out<< ", " << a[i];out<< ']';  }
      |                                ^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5868 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct
3 Correct 4 ms 5868 KB Output is correct
4 Correct 4 ms 5868 KB Output is correct
5 Correct 4 ms 5868 KB Output is correct
6 Correct 5 ms 5996 KB Output is correct
7 Correct 19 ms 7660 KB Output is correct
8 Correct 18 ms 7532 KB Output is correct
9 Correct 23 ms 7660 KB Output is correct
10 Correct 289 ms 23276 KB Output is correct
11 Correct 314 ms 23276 KB Output is correct
12 Correct 262 ms 27884 KB Output is correct
13 Correct 210 ms 23268 KB Output is correct
14 Correct 180 ms 22288 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 23148 KB Output is correct
2 Correct 96 ms 22892 KB Output is correct
3 Correct 87 ms 25216 KB Output is correct
4 Correct 94 ms 25196 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5868 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct
3 Correct 5 ms 5868 KB Output is correct
4 Correct 4 ms 5868 KB Output is correct
5 Correct 4 ms 5868 KB Output is correct
6 Correct 5 ms 5996 KB Output is correct
7 Correct 20 ms 7788 KB Output is correct
8 Correct 285 ms 25708 KB Output is correct
9 Correct 285 ms 25708 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 25708 KB Output is correct
2 Correct 110 ms 25708 KB Output is correct
3 Correct 110 ms 25964 KB Output is correct
4 Correct 108 ms 25836 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5868 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct
3 Correct 4 ms 5868 KB Output is correct
4 Correct 4 ms 5868 KB Output is correct
5 Correct 6 ms 5996 KB Output is correct
6 Correct 22 ms 7660 KB Output is correct
7 Correct 406 ms 24172 KB Output is correct
8 Correct 291 ms 28652 KB Output is correct
9 Correct 242 ms 24292 KB Output is correct
10 Correct 213 ms 23532 KB Output is correct
11 Correct 126 ms 26348 KB Output is correct
12 Correct 124 ms 26312 KB Output is correct
13 Correct 109 ms 28140 KB Output is correct