| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 554344 |
2022-04-28T07:49:12 Z |
leaked |
Pastiri (COI20_pastiri) |
C++17 |
|
719 ms |
346432 KB |
#include <bits/stdc++.h>
#define f first
#define s second
#define m_p make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()
#define vec vector
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=5e5+1;
vec<int> who[N],g[N],gr[2*N];
int used[2*N],n,k,dst[N],cnt[N];
int m;
vec<int> dp[2*N];
vec<vec<int>> pref[2*N],suf[2*N];
struct dsu{
int p[2*N];
int cnt[2*N];
dsu(){
iota(p,p+2*N,0);
fill(cnt,cnt+2*N,1);
}
int get(int v){
return p[v]=(p[v]==v?v:get(p[v]));
}
bool mg(int a,int b){
a=get(a),b=get(b);
if(a==b) return 0;
p[a]=b;cnt[b]+=cnt[a];
return 1;
}
}ds;
void dfs1(int v,int p){
used[v]=1;
///DP
for(auto &z : gr[v]){
if(z==p) continue;
if(used[z]){
assert(false);
}
dfs1(z,v);
}
dp[v].resize(2);
if(v>=n){
dp[v][0]=0;
dp[v][1]=1e9;
for(auto &z : gr[v]){
if(z==p) continue;
pref[v].pb(dp[v]);
vec<int>ndp(2,1e9);
for(int t=0;t<2;t++){
for(int j=0;j<2;j++){
umin(ndp[t|j],dp[z][t]+dp[v][j]);
}
}
for(int t=0;t<2;t++) dp[v][t]=ndp[t];
}
dp[v][0]=0;dp[v][1]=1e9;
reverse(all(gr[v]));
for(auto &z : gr[v]){
if(z==p) continue;
suf[v].pb(dp[v]);
vec<int>ndp(2,1e9);
for(int t=0;t<2;t++){
for(int j=0;j<2;j++){
umin(ndp[t|j],dp[z][t]+dp[v][j]);
}
}
for(int t=0;t<2;t++) dp[v][t]=ndp[t];
}
}
else{
dp[v][0]=0;
dp[v][1]=1;
for(auto &z : gr[v]){
if(z==p) continue;
pref[v].pb(dp[v]);
vec<int>ndp(2,1e9);
// umin(ndp[1],dp[v][0]+1+dp[z][0]);
///dont need it
umin(ndp[1],dp[v][1]+dp[z][0]);
umin(ndp[0],dp[v][0]+dp[z][1]);
umin(ndp[1],dp[v][1]+dp[z][1]);
for(int t=0;t<2;t++) dp[v][t]=ndp[t];
}
dp[v][0]=0;dp[v][1]=1;
reverse(all(gr[v]));
for(auto &z : gr[v]){
if(z==p) continue;
suf[v].pb(dp[v]);
vec<int>ndp(2,1e9);
// umin(ndp[1],dp[v][0]+1+dp[z][0]);
///dont need it
umin(ndp[1],dp[v][1]+dp[z][0]);
umin(ndp[0],dp[v][0]+dp[z][1]);
umin(ndp[1],dp[v][1]+dp[z][1]);
for(int t=0;t<2;t++) dp[v][t]=ndp[t];
}
}
reverse(all(suf[v]));
used[v]=2;
}
vec<int> ans;
void dfs2(int v,int p,int j,int need){
int wi=0;
int cur=0;
if(v<n && j){
ans.pb(v);
wi=1;
}
if(v<n){
int id=0;
for(auto &z : gr[v]){
if(z==p) continue;
for(int t=0;t<2;t++){
int ok=0;
for(int k=0;k<2;k++){
if(((wi|t)|k)==j && (cur+suf[v][id][k]+dp[z][t])){
ok=1;
}
}
if(ok){
cur+=dp[z][t];
dfs2(z,v,t,dp[z][t]);
break;
}
}
}
}
else{
int id=0;
for(auto &z : gr[v]){
if(z==p) continue;
if(j && (cur+suf[v][id][1]+dp[z][0])==need)
dfs2(z,v,0,dp[z][0]);
else
dfs2(z,v,1,dp[z][1]);
}
}
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>k;
fill(dst,dst+n,1e9);
for(int i=1;i<n;i++){
int v,u;
cin>>v>>u;--v;--u;
g[v].pb(u);g[u].pb(v);
}
queue<int>q;
int m=k;
fill(cnt,cnt+n,2);
for(int i=0;i<k;i++){
int v;
cin>>v;--v;
dst[v]=0;
who[v].pb(i);
q.push(v);
}
vec<int> vc;
while(!q.empty()){
int v=q.front();q.pop();
vc.pb(v);
for(auto &z : g[v]){
if(dst[z]==1e9){
dst[z]=dst[v]+1;
q.push(z);
who[z]=who[v];
++cnt[z];
}
else if(dst[z]==dst[v]+1){
++cnt[z];
for(auto &u : who[v])
who[z].pb(u);
}
}
}
reverse(all(vc));
vec<int> ust(2*n,-1);
int tt=0;
int s=0;
///DEBUG
for(auto &i : vc){
if(cnt[i]==1) continue;
++tt;
int ok=0;
s+=sz(who[i]);
// cout<<"I "<<i<<' '<<ok<endl;
for(auto &z : who[i]){
if(ust[ds.get(z+n)]!=tt) ok++;
if(ds.cnt[ds.get(z+n)]==1) ++ok;
ust[ds.get(z+n)]=tt;
}
// cout<<ok<<endl;
if(ok==1) continue;
for(auto &z : who[i]){
gr[i].pb(z+n),gr[z+n].pb(i);
ds.mg(i,z+n);
// cout<<i<<' '<<z+n<<endl;
}
for(auto &z : g[i]){
if(dst[z]==(dst[i]-1))
cnt[z]=1;
}
// for(auto &v : who[i])
// cout<<v<<' ';
// cout<<endl;
}
// dfs1(n,-1);
for(int i=0;i<k;i++){
if(!used[i+n]){
dfs1(i+n,-1);
// ans+=dp[i+n][1];
dfs2(i+n,-1,1,dp[i+n][1]);
}
}
cout<<sz(ans)<<endl;
for(auto &z : ans)
cout<<z+1<<' ';
// cout<<ans<<endl;
// cout<<dp[n][1]<<endl;
// cout<<s<<endl;
return 0;
}
Compilation message
pastiri.cpp: In function 'int main()':
pastiri.cpp:169:9: warning: unused variable 'm' [-Wunused-variable]
169 | int m=k;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
212 ms |
173240 KB |
Output is correct |
| 2 |
Incorrect |
331 ms |
175332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
221 ms |
255460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
157 ms |
254848 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
719 ms |
346432 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
