oj.uz

답안 #399949

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
399949 2021-05-07T00:28:44 Z arwaeystoamneg 동기화 (JOI13_synchronization) C++17
100 / 100
 1218 ms 32088 KB 
// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#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 trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 998244353;//998244353    1000000007

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef arwaeystoamneg
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
#endif
}
template<class T>class segment_tree
{
	struct item
	{
		T sum;
	};
	item single(T i)
	{
		return { i };
	}
	item merge(item x, item y)
	{
		item ans;
		ans.sum = x.sum + y.sum;
		return ans;
	}
	vector<item> tree;
	vector<item>A;
	int height;
	item neutral = { 0 };
public:void build(vector<T>& B)
{
	int	n = B.size();
	height = log2(n + 1) + 1;
	A.rsz(n);
	tree.rsz((1 << height + 1) - 1);
	F0R(i, n)A[i] = single(B[i]);
	A.rsz(1 << height, neutral);
	build(A, 0, 0, (1 << height) - 1);
}
	  void build(vector<item>& A, int v, int tl, int tr)
	  {
		  if (tl == tr)
			  tree[v] = A[tl];
		  else
		  {
			  int mid = (tl + tr) / 2;
			  build(A, 2 * v + 1, tl, mid);
			  build(A, 2 * v + 2, mid + 1, tr);
			  tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
		  }
	  }
public:T query(int l, int r)
{
	return query(0, 0, (1 << height) - 1, l, r).sum;
}
	  item query(int v, int tl, int tr, int l, int r)
	  {
		  if (r<tl || l>tr)return neutral;
		  if (l <= tl && r >= tr)
		  {
			  return tree[v];
		  }
		  int mid = (tl + tr) / 2;
		  return merge(query(2 * v + 1, tl, mid, l, r), query(2 * v + 2, mid + 1, tr, l, r));
	  }
	  //assign
public:void update(int pos, T val)
{
	update(0, 0, (1 << height) - 1, pos, single(val));
}
	  void update(int v, int tl, int tr, int pos, item val)
	  {
		  if (tl == tr)
		  {
			  tree[v] = merge(tree[v], val);
		  }
		  else
		  {
			  int mid = (tl + tr) / 2;
			  if (pos <= mid)
				  update(2 * v + 1, tl, mid, pos, val);
			  else
				  update(2 * v + 2, mid + 1, tr, pos, val);
			  tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
		  }
	  }
};

struct e
{
	int x, y;
	int ans;
	bool a;
	int get(int z)
	{
		return x + y - z;
	}
};
const int MAX = 100005, SZ = 20;
e edge[MAX];
int n, m, q, tin[MAX], order[MAX], sizes[MAX], ptr, parent[MAX], ans[MAX], jump[SZ][MAX];
vi adj[MAX];
segment_tree<ll>sum;
void dfs(int i, int p = -1)
{
	sizes[i] = 1;
	parent[i] = p;
	tin[i] = ptr;
	order[ptr++] = i;
	trav(x, adj[i])
	{
		int j = edge[x].get(i);
		if (j == p)continue;
		dfs(j, i);
		sizes[i] += sizes[j];
	}
}
int get(int i, ll c)
{
	R0F(j, SZ)
	{
		int k = jump[j][i];
		if (k == -1)continue;
		if (sum.query(0, tin[k]) == c)i = k;
	}
	return i;
}
int main()
{
	setIO("test1");
	cin >> n >> m >> q;
	F0R(i, n - 1)
	{
		int x, y;
		cin >> x >> y;
		edge[i] = { --x,--y,0,0 };
		adj[x].pb(i);
		adj[y].pb(i);
	}
	vll temp(n + 1, 1);
	sum.build(temp);
	dfs(0);
	F0R(i, n - 1)if (parent[edge[i].x] == edge[i].y)swap(edge[i].x, edge[i].y);
	fill(ans, ans + n, 1);
	F0R(i, n)jump[0][i] = parent[i];
	F0R(i, SZ - 1)
	{
		F0R(j, n)
		{
			jump[i + 1][j] = (jump[i][j] == -1 ? -1 : jump[i][jump[i][j]]);
		}
	}
	ll cur = inf;
	while (m--)
	{
		int i;
		cin >> i;
		i--;
		if (edge[i].a == 0)
		{
			ll c = sum.query(0, tin[edge[i].x]);
			int j = get(edge[i].x, c);
			ans[j] += ans[edge[i].y] - edge[i].ans;
			ll d = sum.query(0, tin[j]) - sum.query(0, tin[edge[i].y]);
			sum.update(tin[edge[i].y], d);
			sum.update(tin[edge[i].y] + sizes[edge[i].y], -d);
		}
		else
		{
			ll c = sum.query(0, tin[edge[i].x]);
			int j = get(edge[i].x, c);
			edge[i].ans = ans[j];
			ans[edge[i].y] = ans[j];
			sum.update(tin[edge[i].y], cur);
			sum.update(tin[edge[i].y] + sizes[edge[i].y], -cur);
			cur += inf;
		}
		edge[i].a ^= 1;
	}
	while (q--)
	{
		int i;
		cin >> i;
		i--;
		ll c = sum.query(0, tin[i]);
		int j = get(i, c);
		cout << ans[j] << endl;
	}
}

Compilation message

synchronization.cpp: In instantiation of 'void segment_tree<T>::build(std::vector<_Tp>&) [with T = long long int]':
synchronization.cpp:186:16:   required from here
synchronization.cpp:80:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   80 |  tree.rsz((1 << height + 1) - 1);
      |                 ~~~~~~~^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 3 ms 2764 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 4 ms 2892 KB Output is correct
7 Correct 31 ms 4988 KB Output is correct
8 Correct 31 ms 4992 KB Output is correct
9 Correct 31 ms 4940 KB Output is correct
10 Correct 500 ms 23476 KB Output is correct
11 Correct 486 ms 23348 KB Output is correct
12 Correct 1004 ms 31156 KB Output is correct
13 Correct 202 ms 23212 KB Output is correct
14 Correct 299 ms 22824 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 244 ms 27060 KB Output is correct
2 Correct 233 ms 26920 KB Output is correct
3 Correct 276 ms 30484 KB Output is correct
4 Correct 285 ms 30488 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2768 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 6 ms 3072 KB Output is correct
7 Correct 60 ms 5808 KB Output is correct
8 Correct 1218 ms 32088 KB Output is correct
9 Correct 1147 ms 31880 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1147 ms 31836 KB Output is correct
2 Correct 463 ms 31588 KB Output is correct
3 Correct 460 ms 31696 KB Output is correct
4 Correct 454 ms 31736 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2768 KB Output is correct
3 Correct 2 ms 2672 KB Output is correct
4 Correct 2 ms 2776 KB Output is correct
5 Correct 5 ms 2892 KB Output is correct
6 Correct 39 ms 5036 KB Output is correct
7 Correct 621 ms 24284 KB Output is correct
8 Correct 1143 ms 31900 KB Output is correct
9 Correct 260 ms 24388 KB Output is correct
10 Correct 343 ms 24216 KB Output is correct
11 Correct 314 ms 28228 KB Output is correct
12 Correct 321 ms 28260 KB Output is correct
13 Correct 456 ms 31668 KB Output is correct