oj.uz

Submission #1115358

# Submission time Handle Problem Language Result Execution time Memory
1115358 2024-11-20T11:22:35 Z 0pt1mus23 Pastiri (COI20_pastiri) C++14
100 / 100
 452 ms 81828 KB 
#pragma GCC optimize("Ofast,unroll-loops")

// el psy congroo
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 998244353, sze = 5e5+23, inf = LLONG_MAX, LG = 17;
vector<int> graph[sze];
int used[sze];
int dist[sze];
int d[sze];
int hig[sze];

void dfs(int node,int par=0,int mx=-23,int best=1){
    if( (d[node] + dist[node] )> mx ){
        mx=d[node]+dist[node];
        best=node;
    }
    hig[node]=best;
    for(auto v:graph[node]){
        if(v!=par){
            d[v]=d[node]+1;
            dfs(v,node,mx,best);
        }
    }
}
void sil(int node,int par=0){
    used[node]=1;
    for(auto v:graph[node]){
        if(!used[v] && dist[node]==dist[v]+1){
            sil(v,node);
        }
    }
}
void fast(){
    int n,k;
    cin>>n>>k;
    for(int i =1;i<n;i++){
        int u,v;
        cin>>u>>v;
        graph[u].pb(v);
        graph[v].pb(u);
    }
    for(int i =1;i<=n;i++){
        dist[i]=inf;
    }

    queue<int> q;

    vector<int> sheep(k);
    for(auto &v:sheep){
        cin>>v;
        q.push(v);
        dist[v]=0;
    }

    while(!q.empty()){
        int node = q.front();q.pop();
        for(auto v:graph[node]){
            if(dist[v] > dist[node]+1){
                dist[v]=dist[node]+1;
                q.push(v);
            }
        }
    }
    dfs(1);
    sort(all(sheep),[&](int a,int b){
        return d[a]>d[b];
    });
    vector<int> ans;
    for(auto v:sheep){
        if(!used[v]){
            sil(hig[v]);
            ans.pb(hig[v]);
        }
    }

    cout<<ans.size()<<"\n";
    for(auto v:ans) cout<<v<<" ";cout<<endl;


}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tt = 1;
    // cin>>tt;
 
    while(tt--){
        fast();
    }
    return 0;
}

Compilation message

pastiri.cpp: In function 'void fast()':
pastiri.cpp:85:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   85 |     for(auto v:ans) cout<<v<<" ";cout<<endl;
      |     ^~~
pastiri.cpp:85:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   85 |     for(auto v:ans) cout<<v<<" ";cout<<endl;
      |                                  ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 69672 KB Output is correct
2 Correct 164 ms 71364 KB Output is correct
3 Correct 162 ms 71396 KB Output is correct
4 Correct 249 ms 81828 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15760 KB Output is correct
2 Correct 7 ms 15696 KB Output is correct
3 Correct 277 ms 53632 KB Output is correct
4 Correct 282 ms 56620 KB Output is correct
5 Correct 350 ms 49980 KB Output is correct
6 Correct 452 ms 52296 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15440 KB Output is correct
2 Correct 6 ms 15440 KB Output is correct
3 Correct 5 ms 15440 KB Output is correct
4 Correct 6 ms 15440 KB Output is correct
5 Correct 6 ms 15452 KB Output is correct
6 Correct 6 ms 15440 KB Output is correct
7 Correct 6 ms 15440 KB Output is correct
8 Correct 5 ms 15440 KB Output is correct
9 Correct 6 ms 15608 KB Output is correct
10 Correct 5 ms 15440 KB Output is correct
11 Correct 5 ms 15440 KB Output is correct
12 Correct 6 ms 15440 KB Output is correct
13 Correct 7 ms 15440 KB Output is correct
14 Correct 5 ms 15440 KB Output is correct
15 Correct 8 ms 15432 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 53568 KB Output is correct
2 Correct 350 ms 53520 KB Output is correct
3 Correct 404 ms 58848 KB Output is correct
4 Correct 366 ms 49992 KB Output is correct
5 Correct 268 ms 51676 KB Output is correct
6 Correct 396 ms 62508 KB Output is correct
7 Correct 431 ms 60564 KB Output is correct
8 Correct 436 ms 59480 KB Output is correct
9 Correct 392 ms 50232 KB Output is correct
10 Correct 339 ms 49992 KB Output is correct
11 Correct 281 ms 56120 KB Output is correct
12 Correct 268 ms 59896 KB Output is correct
13 Correct 276 ms 63064 KB Output is correct
14 Correct 217 ms 56840 KB Output is correct
15 Correct 58 ms 26952 KB Output is correct
16 Correct 385 ms 48716 KB Output is correct
17 Correct 281 ms 53000 KB Output is correct
18 Correct 313 ms 45456 KB Output is correct
19 Correct 334 ms 57928 KB Output is correct
20 Correct 389 ms 59932 KB Output is correct
21 Correct 427 ms 52552 KB Output is correct
22 Correct 397 ms 53064 KB Output is correct