# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
957642 | guagua0407 | Synchronization (JOI13_synchronization) | C++17 | 143 ms | 262144 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
const int mxn=1e5+5;
vector<int> adj[mxn];
bitset<mxn> dp[mxn];
int depth[mxn];
bool ok[mxn];
void dfs(int v,int p=0){
depth[v]=depth[p]+1;
dp[v][v]=1;
for(auto u:adj[v]){
if(u==p) continue;
dfs(u,v);
}
}
int main() {_
int n,m,q;
cin>>n>>m>>q;
vector<pair<int,int>> e(n-1);
for(int i=0;i<n-1;i++){
int a,b;
cin>>a>>b;
e[i]={a,b};
adj[a].push_back(b);
adj[b].push_back(a);
}
vector<int> qs;
for(int i=0;i<m;i++){
int x;
cin>>x;
x--;
qs.push_back(x);
}
int root;
cin>>root;
dfs(root);
for(auto x:qs){
if(ok[x]){
ok[x]=false;
continue;
}
ok[x]=true;
int a=e[x].f;
int b=e[x].s;
if(depth[a]>depth[b]) swap(a,b);
dp[a]|=dp[b];
}
cout<<dp[root].count()<<'\n';
return 0;
}
//maybe its multiset not set
//yeeorz
//laborz
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |