| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 397401 | 2021-05-02T04:01:27 Z | order999 | 동기화 (JOI13_synchronization) | C++14 | 4 ms | 588 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();
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 3 ms | 536 KB | Execution killed with signal 11 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 4 ms | 588 KB | Execution killed with signal 11 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 3 ms | 588 KB | Execution killed with signal 11 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 3 ms | 588 KB | Execution killed with signal 11 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 3 ms | 508 KB | Execution killed with signal 11 |
| 2 | Halted | 0 ms | 0 KB | - |