oj.uz

답안 #397402

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
397402 2021-05-02T04:03:55 Z order999 동기화 (JOI13_synchronization) C++14
0 / 100
 222 ms 17548 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
//	freopen((s + ".in").c_str(), "r", stdin);
//	freopen((s + ".out").c_str(), "w", stdout);
}

int n, m, q;
vector<vector<int>> adj;
vector<pair<int, int>> edges;
vector<int> d;
vector<int> c;
int c1, c2;

void init(string str)
{
	setIO(str);
	string s;
	cin >> n >> m >> q;

	adj.resize(n);
	for (int i = 1; i < n; i++)
	{
		cin >> c1 >> c2;
		c1--; c2--;
		// edge
		edges.push_back({ c1, c2 });
		// tree
		adj[c1].push_back(c2);
		adj[c2].push_back(c1);
	}
	for (int i = 0; i < m ; i++)
	{
		cin >> c1;
		c1--;
		d.push_back(c1);
	}
	for (int i = 0; i < q; i++)
	{
		cin >> c1;
		c1--;
		c.push_back(c1);
	}
}

vector<int> depth;
vector<int> anc;
vector<int> info;
void dfs(int u, int p, int d)
{
	depth[u] = d;
	for (auto v : adj[u])
	{
		if (v == p)	continue;
		if (depth[v] != -1)	continue;
		dfs(v, u, d+1);
	}
}

void solve()
{
	depth.resize(n, -1);
	dfs(0, -1, 0);

	// keeps adding edges
	// when next move is to remove edges do the following
	// generate connected components, all nodes in the CC contains the same information, update the information before the cut
	// to accomplish the following need the folling queries
	//	- add an edge
	//	- update the values for this connected component
	//	- remove an edge
	//  - query the value for a node
	// important observations: 
	// use the root of the tree (one connected component), need a way to find this root without dfs?
	// store the elemnts of a CC in a set or just the count is enough?

	vector<int> ce, co;
	ce.resize(n - 1, 0);
	co.resize(n - 1, 0);
	anc.resize(n);			// anc[i] is the lowest (close to root) node in node i's connected component
	info.resize(n);
	for (int i = 0; i < n; i++)
	{
		anc[i] = i;
		info[i] = 1;
	}

	//modifying the edges
	for (int i = 0; i < m; i++)
	{
		ce[d[i]]++;
		int a = edges[d[i]].first, b = edges[d[i]].second;
		// note that a, b will never at the same depth for tree
		if (depth[anc[a]] > depth[anc[b]])
			swap(a, b);

		if (ce[d[i]] & 1)	// add edge d[i]
		{
			// merge b into a's connected field
			info[anc[a]] += info[anc[b]] - co[d[i]];	// now put the count of info from b to a, remove the common info between a and b
			info[anc[b]] = 0;
			anc[b] = anc[a];
		}
		else // remove edge d[i]
		{
			// connected component with a still have the same root, b became the root of the other connected component
			anc[b] = b;
			info[b] = info[anc[a]];
			// store the number of common nodes between CC a and CC b on edge 
			co[d[i]] = info[anc[a]];
		}
	}

	// query
	for (int i = 0; i < q; i++)
	{
		int a = c[i];
		cout << info[anc[a]] << endl;
	}
}

int main()
{
	init("synchronization");

	solve();
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 13892 KB Output is correct
2 Correct 52 ms 13676 KB Output is correct
3 Incorrect 48 ms 15544 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 222 ms 17548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -