oj.uz

Submission #243697

# Submission time Handle Problem Language Result Execution time Memory
243697 2020-07-01T14:58:57 Z xiryss Synchronization (JOI13_synchronization) C++17
100 / 100
 460 ms 21224 KB 
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
/*#pragma GCC optimize("section-anchors")
#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
#pragma GCC optimize("vpt")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("move-loop-invariants")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize("function-sections")
#pragma GCC optimize("data-sections")
#pragma GCC optimize("branch-target-load-optimize")
#pragma GCC optimize("branch-target-load-optimize2")
#pragma GCC optimize("btr-bb-exclusive")*/
//#pragma comment(linker, "/STACK:367077216")
#define _CRT_SECURE_NO_WARNINGS
#include <chrono>
#include <set>
#include <map>
#include <deque>
#include <string>
#include <cstdint>
#include <cmath>
#include <queue>
#include <cassert>
#include <random>
#include <bitset>
#include <iomanip>
#include <numeric>
#include <time.h>//////////////
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
//++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
//#define endl '\n'
#define mp make_pair
#define pbc push_back
#define pob pop_back()
#define empb emplace_back
#define queuel queue<long long>
#define sqr(a) ((a) * (a))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pin(p) cin >> p.first >> p.second;
#define uniq(a) sort(all(a));(a).resize(unique(all(a)) - a.begin());
#define rev(v) reverse(v.begin(), v.end());
#define sout(s, c) for (auto i : s) cout << i << c;
#define pout(p) cout << p.first << " " << p.second;
#define er(v, l, r) erase(v.begin() + l, v.begin() + r);
#define vin(v) for (ll i = 0; i < v.size(); ++i) cin >> v[i];
#define vout(v, c) for (int i = 0; i < v.size(); ++i) cout << v[i] << c;
#define pushi(v, a) for (int i = 0; i < a.size(); ++i) v.push_back(a[i]);
#define fastio() ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); srand(time(NULL))
#define dab(v) for(auto i:v)cout<<i<<' ';
#define sp system("pause")
//++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
using namespace std;
//++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
//++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
mt19937 rnd(time(0) + 228 + 'k' + 'e' + 'k' + 'e' + 'r' + 'o' + 'f' + 'e' + 'y');
const ld EPS = 1e-10;
bool checkprime(int x)
{
	for (int i = 2; i * i <= x; ++i) if (x % i == 0) return 0;
	return 1;
}
const ld PI = acos(-1);
const int MOD7 = 1000000007;
const int MOD9 = 1000000009;
int mod = MOD7;
const int inf = 1e9;
const int MAXN = 1e5 + 1;
int f[MAXN * 2];
vector<int> g[MAXN];
vector<pair<int, int>> e;
int  n, m, q;
void add(int i, int x)
{
	for (; i < 2*MAXN; i |= (i + 1)) f[i] += x;
}
int get(int r)
{
	int ans = 0;
	for (; r >= 0; r = (r & (r + 1)) - 1) ans += f[r];
	return ans;
}
const int lgg = 17;
int tl = 0;
int tin[MAXN];
int up[MAXN][lgg];
int h[MAXN];
int tout[MAXN];
void dfs(int v, int p)
{
	tin[v] = tl++;
	up[v][0] = p;
	h[v] = h[p] + 1;
	for (int i = 1; i < lgg; ++i)
	{
		up[v][i] = up[up[v][i - 1]][i - 1];
	}
	for (int i : g[v])
	{
		if (i == p) continue;
		dfs(i, v);
	}
	tout[v] = tl++;
}
int a[MAXN];
int c[MAXN];
bool pp(int a, int b)
{
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b)
{
	if (pp(a, b)) return  a;
	if (pp(b, a)) return b;
	for (int i = lgg - 1; i >= 0; --i)
	{
		if (pp(up[a][i], b)) a = up[a][i];
	}
	return a;
}
int toroot(int v)
{
	return get(tin[v]);
}
int pquery(int a, int b)
{
	return toroot(a) + toroot(b) - 2 * toroot(lca(a, b));
}
void upd(int v, int x)
{
	add(tin[v], x);
	add(tout[v] + 1, -x);
}
int exist(int a, int b)
{
	return pquery(a, b) == h[b] - h[a];
}
int getroot(int v)
{
	int tv = v;
	for (int i = lgg - 1; i >= 0; --i) if (exist(up[tv][i], v)) tv = up[tv][i];
	return tv;
}
bool on[MAXN];
signed main()
{
	fastio();
	cin >> n >> m >> q;
	for (int i = 0; i < n - 1; ++i)
	{
		int a, b;
		cin >> a >> b;
		e.pbc({ a,b });
		g[a].pbc(b);
		g[b].pbc(a);
	}
	h[1] = -1;
	dfs(1, 1);
	for (int i = 0; i < e.size(); ++i)
	{
		if (h[e[i].first] > h[e[i].second]) swap(e[i].first, e[i].second);
	}
	fill(a, a + MAXN, 1);
	for (int i = 0; i < m; ++i)
	{
		int  x;
		cin >> x;
		--x;
		int fs = e[x].first, ss = e[x].second;
		if (!on[x])
		{
			int xxx = getroot(fs);
			a[fs] = a[xxx];
			a[ss] = a[fs] + a[ss] - c[ss];
			a[fs] = a[ss];
			a[xxx] = a[fs];
			upd(ss, 1);
		}
		else
		{
			a[ss] = a[getroot(ss)];
			c[ss] = a[ss];
			upd(ss, -1);
		}
		on[x] ^= 1;
	}
	for (int i = 0; i < q; ++i)
	{
		int x;
		cin >> x;
		cout << a[getroot(x)] << '\n';
	}
	//sp;
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:172:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < e.size(); ++i)
                  ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3200 KB Output is correct
2 Correct 6 ms 3200 KB Output is correct
3 Correct 6 ms 3200 KB Output is correct
4 Correct 6 ms 3200 KB Output is correct
5 Correct 6 ms 3200 KB Output is correct
6 Correct 8 ms 3328 KB Output is correct
7 Correct 24 ms 4480 KB Output is correct
8 Correct 25 ms 4480 KB Output is correct
9 Correct 23 ms 4480 KB Output is correct
10 Correct 317 ms 16236 KB Output is correct
11 Correct 353 ms 16232 KB Output is correct
12 Correct 387 ms 20844 KB Output is correct
13 Correct 158 ms 16492 KB Output is correct
14 Correct 178 ms 15852 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 18412 KB Output is correct
2 Correct 136 ms 18284 KB Output is correct
3 Correct 163 ms 20456 KB Output is correct
4 Correct 161 ms 20456 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3200 KB Output is correct
2 Correct 7 ms 3200 KB Output is correct
3 Correct 7 ms 3200 KB Output is correct
4 Correct 6 ms 3200 KB Output is correct
5 Correct 6 ms 3200 KB Output is correct
6 Correct 8 ms 3328 KB Output is correct
7 Correct 34 ms 4984 KB Output is correct
8 Correct 452 ms 21144 KB Output is correct
9 Correct 460 ms 20972 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 21100 KB Output is correct
2 Correct 271 ms 21224 KB Output is correct
3 Correct 269 ms 21100 KB Output is correct
4 Correct 261 ms 21100 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3200 KB Output is correct
2 Correct 6 ms 3200 KB Output is correct
3 Correct 7 ms 3200 KB Output is correct
4 Correct 6 ms 3200 KB Output is correct
5 Correct 8 ms 3328 KB Output is correct
6 Correct 34 ms 4528 KB Output is correct
7 Correct 387 ms 16488 KB Output is correct
8 Correct 456 ms 21100 KB Output is correct
9 Correct 190 ms 17128 KB Output is correct
10 Correct 223 ms 16616 KB Output is correct
11 Correct 176 ms 19048 KB Output is correct
12 Correct 172 ms 19144 KB Output is correct
13 Correct 260 ms 21096 KB Output is correct