#include <bits/stdc++.h>
using namespace std;
int n,m,q;
typedef pair<int,int> P;
P edge[100000];
int ont[100000];
typedef pair<int,int> P;
vector<P> adj[100001];
int dp[500000];
int cnt=0;
int ind[100001];
typedef pair<P,int> Pi;
vector<int> put[100001];
vector<int> er[100001];
set<int> s;
int le[500000];
int ri[500000];
int ldp[500000];
int rdp[500000];
int pos[500000];
int lv(int now) {
if (ldp[now]!=-1) {
return ldp[now];
}
if (le[now]==-1) {
return ldp[now]=now;
}
return ldp[now]=lv(le[now]);
}
int rv(int now) {
if (rdp[now]!=-1) {
return rdp[now];
}
if (ri[now]==-1) {
return rdp[now]=now;
}
return rdp[now]=rv(ri[now]);
}
int main(void) {
scanf("%d %d %d",&n,&m,&q);
for(int i=1;i<n;i++) {
int a,b;
scanf("%d %d",&a,&b);
a--;
b--;
adj[a].push_back(P(b,i));
adj[b].push_back(P(a,i));
edge[i]=P(a,b);
}
memset(ont,-1,sizeof(ont));
for(int i=0;i<m;i++) {
int x;
scanf("%d",&x);
if (ont[x]!=-1) {
//s[x].insert(P(ont[x],i-1));
ont[x]=-1;
er[i-1].push_back(x);
}
else {
ont[x]=i;
put[i].push_back(x);
}
}
for(int i=1;i<n;i++) {
if (ont[i]!=-1) {
//s[i].insert(P(ont[i],m-1));
er[m-1].push_back(i);
}
s.insert(i);
}
memset(dp,-1,sizeof(dp));
memset(ind,-1,sizeof(ind));
memset(le,-1,sizeof(le));
memset(ri,-1,sizeof(ri));
for(int i=0;i<m;i++) {
for(int j=0;j<put[i].size();j++) {
int now=put[i][j];
ind[now]=cnt;
pos[ind[now]]=now;
cnt++;
s.erase(now);
}
for(int j=0;j<er[i].size();j++) {
int now=er[i][j];
int idx=ind[now];
s.insert(now);
auto iter=s.lower_bound(now);
if (iter!=s.begin()) {
iter--;
le[idx]=ind[(*iter)];
iter++;
}
iter++;
if (iter!=s.end()) {
ri[idx]=ind[(*iter)];
iter++;
}
}
}
memset(ldp,-1,sizeof(ldp));
memset(rdp,-1,sizeof(rdp));
for(int i=0;i<q;i++) {
int st;
scanf("%d",&st);
st--;
int ret=0;
if (ind[st]!=-1) {
int idx=ind[st];
idx=lv(idx);
ret+=st-pos[idx]+1;
}
if (ind[st+1]!=-1) {
int idx=ind[st+1];
idx=rv(idx);
ret+=pos[idx]-st;
}
printf("%d\n",ret);
}
}
Compilation message
synchronization.cpp: In function 'int main()':
synchronization.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int j=0;j<put[i].size();j++) {
| ~^~~~~~~~~~~~~~
synchronization.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int j=0;j<er[i].size();j++) {
| ~^~~~~~~~~~~~~
synchronization.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
44 | scanf("%d %d %d",&n,&m,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf("%d %d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~~
synchronization.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | scanf("%d",&x);
| ~~~~~^~~~~~~~~
synchronization.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | scanf("%d",&st);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
17876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
76 ms |
37188 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
17876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
61 ms |
31884 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
17920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
