oj.uz

Submission #243696

# Submission time Handle Problem Language Result Execution time Memory
243696 2020-07-01T14:58:10 Z xiryss Synchronization (JOI13_synchronization) C++17
100 / 100
 666 ms 24044 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 up[a][0];
}
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])
		{
			a[fs] = a[getroot(fs)];
			a[ss] = a[fs] + a[ss] - c[ss];
			a[fs] = a[ss];
			a[getroot(fs)] = 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 3072 KB Output is correct
2 Correct 6 ms 3200 KB Output is correct
3 Correct 6 ms 3200 KB Output is correct
4 Correct 7 ms 3200 KB Output is correct
5 Correct 7 ms 3200 KB Output is correct
6 Correct 9 ms 3328 KB Output is correct
7 Correct 33 ms 4480 KB Output is correct
8 Correct 28 ms 4480 KB Output is correct
9 Correct 34 ms 4480 KB Output is correct
10 Correct 408 ms 16744 KB Output is correct
11 Correct 363 ms 18540 KB Output is correct
12 Correct 490 ms 23132 KB Output is correct
13 Correct 166 ms 18412 KB Output is correct
14 Correct 238 ms 17640 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 18412 KB Output is correct
2 Correct 169 ms 20200 KB Output is correct
3 Correct 245 ms 22184 KB Output is correct
4 Correct 239 ms 22192 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 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 11 ms 3328 KB Output is correct
7 Correct 40 ms 4984 KB Output is correct
8 Correct 569 ms 22124 KB Output is correct
9 Correct 563 ms 23916 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 20976 KB Output is correct
2 Correct 374 ms 23408 KB Output is correct
3 Correct 342 ms 23400 KB Output is correct
4 Correct 349 ms 23532 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 7 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 8 ms 3328 KB Output is correct
6 Correct 36 ms 4480 KB Output is correct
7 Correct 524 ms 17900 KB Output is correct
8 Correct 548 ms 24044 KB Output is correct
9 Correct 208 ms 19564 KB Output is correct
10 Correct 312 ms 19084 KB Output is correct
11 Correct 207 ms 21612 KB Output is correct
12 Correct 211 ms 21612 KB Output is correct
13 Correct 332 ms 23400 KB Output is correct