oj.uz

Submission #1095829

# Submission time Handle Problem Language Result Execution time Memory
1095829 2024-10-03T09:22:30 Z cpptowin Pastiri (COI20_pastiri) C++17
100 / 100
 387 ms 137552 KB 
#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define inf (int)1e18
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1 << j))
#define onbit(i, j) (i | (1 << j))
#define vi vector<int>
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
int n, k;
vi ke[maxn], adj[maxn], save;
pii edge[maxn];
int h[maxn], d[maxn], a[maxn];
bool sheep[maxn], vis[maxn];
void bfs()
{
    memset(d,-1,sizeof d);
    queue<int> q;
    fo(i, 1, n) if (sheep[i])
    {
        q.push(i), d[i] = 0;
    }
    while (q.size())
    {
        int u = q.front();
        q.pop();
        for (int v : ke[u])
        {
            if (d[v] == -1)
            {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
}
void dfs(int u, int par = 0, int now = 0)
{
    if (d[now] + h[now] < d[u] + h[u])
        now = u;
    a[u] = now;
    for (int v : ke[u])
    {
        if (v == par)
            continue;
        h[v] = h[u] + 1;
        dfs(v, u, now);
    }
}
void dfs1(int u, int par = 0)
{
    vis[u] = 1;
    for (int v : ke[u]) if(d[u] == d[v] + 1)
    {
        if (vis[v])
            continue;
        dfs1(v, u);
    }
}
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    fo(i, 1, n - 1)
    {
        int u, v;
        cin >> u >> v;
        ke[u].pb(v);
        ke[v].pb(u);
        edge[i] = {u, v};
    }
    fo(i, 1, k)
    {
        int x;
        cin >> x;
        sheep[x] = 1;
    }
    int node = 1;
    fo(i, 1, n) if (sheep[i])
    {
        node = i;
        break;
    }
    bfs();
    dfs(node);
    a[node] = node;
    fo(i, 1, n) if (sheep[i]) adj[h[i]].pb(i);
    fod(i, n, 0) for (int it : adj[i]) save.pb(it);
    vi ans;
    for (int it : save) if(!vis[it])
    {
        ans.pb(a[it]);
        dfs1(a[it]);
    }
    cout << ans.size();
    en;
    for (int it : ans)
        cout << it << ' ';
    en;
}

Compilation message

pastiri.cpp:91:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   91 | main()
      | ^~~~
pastiri.cpp: In function 'int main()':
pastiri.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
pastiri.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 112952 KB Output is correct
2 Correct 197 ms 121424 KB Output is correct
3 Correct 177 ms 121568 KB Output is correct
4 Correct 206 ms 137552 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 51536 KB Output is correct
2 Correct 24 ms 51544 KB Output is correct
3 Correct 253 ms 82512 KB Output is correct
4 Correct 252 ms 84316 KB Output is correct
5 Correct 305 ms 82000 KB Output is correct
6 Correct 387 ms 87204 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51280 KB Output is correct
2 Correct 27 ms 51488 KB Output is correct
3 Correct 25 ms 51452 KB Output is correct
4 Correct 22 ms 51292 KB Output is correct
5 Correct 24 ms 51292 KB Output is correct
6 Correct 24 ms 51292 KB Output is correct
7 Correct 25 ms 51292 KB Output is correct
8 Correct 24 ms 51284 KB Output is correct
9 Correct 24 ms 51292 KB Output is correct
10 Correct 24 ms 51292 KB Output is correct
11 Correct 23 ms 51280 KB Output is correct
12 Correct 28 ms 51288 KB Output is correct
13 Correct 22 ms 51284 KB Output is correct
14 Correct 27 ms 51716 KB Output is correct
15 Correct 21 ms 51288 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 83532 KB Output is correct
2 Correct 274 ms 83276 KB Output is correct
3 Correct 292 ms 87040 KB Output is correct
4 Correct 272 ms 82276 KB Output is correct
5 Correct 223 ms 81224 KB Output is correct
6 Correct 304 ms 91808 KB Output is correct
7 Correct 356 ms 91116 KB Output is correct
8 Correct 341 ms 90368 KB Output is correct
9 Correct 361 ms 82460 KB Output is correct
10 Correct 291 ms 82000 KB Output is correct
11 Correct 235 ms 84308 KB Output is correct
12 Correct 276 ms 89172 KB Output is correct
13 Correct 277 ms 91756 KB Output is correct
14 Correct 214 ms 85548 KB Output is correct
15 Correct 58 ms 56676 KB Output is correct
16 Correct 294 ms 80280 KB Output is correct
17 Correct 210 ms 81604 KB Output is correct
18 Correct 269 ms 76884 KB Output is correct
19 Correct 315 ms 90024 KB Output is correct
20 Correct 360 ms 93944 KB Output is correct
21 Correct 270 ms 82428 KB Output is correct
22 Correct 286 ms 83284 KB Output is correct