oj.uz

Submission #759071

# Submission time Handle Problem Language Result Execution time Memory
759071 2023-06-15T18:01:24 Z Ronin13 Pastiri (COI20_pastiri) C++14
100 / 100
 593 ms 76828 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 500001;

int x[nmax], d[nmax];
bool active[nmax];
int dp[nmax];
vector <vector <int> > g(nmax);

void dfs(int v, int e = -1){
    for(int to : g[v]){
        if(to == e) continue;
        dfs(to, v);
        d[v] = min(d[v], d[to] + 1);
    }
}

vector <int> ans;

void DFS(int v, int e = -1){
    for(int to : g[v]){
        if(to == e) continue;
        DFS(to, v);
        active[v] |= active[to];
        dp[v] = max(dp[v], dp[to] - 1);
    }
    if(!active[v])
        return;
    if(v == 1 && active[v]){
        if(dp[v] >= d[v]) return;
        ans.pb(v);
        dp[v] = -1;
        return;
    }

    if(x[e] == d[v] + 1){
        if(dp[v] >= d[v]) active[v] = false;
        return;
    }
    active[v] = false;
    if(dp[v] >= d[v])
        return;
    dp[v] = d[v];
    ans.pb(v);
}

int main(){
    //ios_base::sync_with_stdio(false); cin.tie(0);
    int n, k;
    scanf("%d%d",&n, &k);
    for(int i = 1; i < n; i++){
        int u, v; scanf("%d%d", &u, &v);
        g[u].pb(v);
        g[v].pb(u);
    }
    //int k; cin >> k;
    for(int i = 1; i <= n; i++){
        x[i] = d[i] = 1e9;
        dp[i] = -1e9;
    }
    queue <int> q;
    for(int i = 1; i <= k; ++i){
        int y; scanf("%d", &y);
        q.push(y);
        active[y] = true;
        x[y] = d[y] = 0;
    }
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(int to : g[v]){
            if(x[to] <= x[v] + 1) continue;
            x[to] = x[v] + 1;
            q.push(to);
        }
    }
    dfs(1);
    DFS(1);
    printf("%d\n", ans.size()); //ans.size() << "\n";
    sort(ans.begin(), ans.end());
    for(int to : ans)
        printf("%d ", to);
    return 0;
}

Compilation message

pastiri.cpp: In function 'int main()':
pastiri.cpp:87:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   87 |     printf("%d\n", ans.size()); //ans.size() << "\n";
      |             ~^     ~~~~~~~~~~
      |              |             |
      |              int           std::vector<int>::size_type {aka long unsigned int}
      |             %ld
pastiri.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%d%d",&n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~
pastiri.cpp:60:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         int u, v; scanf("%d%d", &u, &v);
      |                   ~~~~~^~~~~~~~~~~~~~~~
pastiri.cpp:71:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         int y; scanf("%d", &y);
      |                ~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 73176 KB Output is correct
2 Correct 177 ms 73184 KB Output is correct
3 Correct 177 ms 73160 KB Output is correct
4 Correct 224 ms 76828 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 11 ms 12236 KB Output is correct
3 Correct 381 ms 34552 KB Output is correct
4 Correct 441 ms 36968 KB Output is correct
5 Correct 531 ms 34160 KB Output is correct
6 Correct 555 ms 37612 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 8 ms 12132 KB Output is correct
3 Correct 7 ms 12140 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 7 ms 12172 KB Output is correct
7 Correct 6 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 7 ms 12108 KB Output is correct
10 Correct 6 ms 12116 KB Output is correct
11 Correct 6 ms 12040 KB Output is correct
12 Correct 6 ms 12040 KB Output is correct
13 Correct 6 ms 12116 KB Output is correct
14 Correct 7 ms 12116 KB Output is correct
15 Correct 6 ms 12116 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 35140 KB Output is correct
2 Correct 474 ms 34960 KB Output is correct
3 Correct 506 ms 36248 KB Output is correct
4 Correct 495 ms 34088 KB Output is correct
5 Correct 376 ms 32092 KB Output is correct
6 Correct 441 ms 49192 KB Output is correct
7 Correct 523 ms 47148 KB Output is correct
8 Correct 471 ms 46792 KB Output is correct
9 Correct 578 ms 40796 KB Output is correct
10 Correct 549 ms 40788 KB Output is correct
11 Correct 349 ms 42708 KB Output is correct
12 Correct 309 ms 45840 KB Output is correct
13 Correct 328 ms 47292 KB Output is correct
14 Correct 307 ms 44500 KB Output is correct
15 Correct 49 ms 16860 KB Output is correct
16 Correct 493 ms 38592 KB Output is correct
17 Correct 324 ms 38944 KB Output is correct
18 Correct 442 ms 35496 KB Output is correct
19 Correct 496 ms 47300 KB Output is correct
20 Correct 593 ms 52004 KB Output is correct
21 Correct 461 ms 40868 KB Output is correct
22 Correct 491 ms 41608 KB Output is correct