oj.uz

Submission #381595

# Submission time Handle Problem Language Result Execution time Memory
381595 2021-03-25T10:41:08 Z topovik Pastiri (COI20_pastiri) C++14
0 / 100
 1000 ms 228548 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define len(x) x.size()
#define debug(x) cout << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 1e6;

vector <int> a[N];
vector <int> dist[N];

vector <int> nearest[N];
vector <int> nearest_sheep[N];
vector <int> order;
bool mrk[N];
int kol[N];
int nom[N];
int pos[N];
int k;

void Calc_Dist(int x, int y, int ds, int type)
{
    dist[type][x] = ds;
    for (int i = 0; i < a[x].size(); i++)
        if (a[x][i] != y) Calc_Dist(a[x][i], x, ds + 1, type);
}

void Delete_Sheep(int x)
{
    if (mrk[x]) return;
    mrk[x] = 1;
    for (int i = 0; i < nearest[x].size(); i++) kol[nearest[x][i]]--;
}

void Calc_Order(int x, int y)
{
    for (int i = 0; i < a[x].size(); i++)
        if (a[x][i] != y) Calc_Order(a[x][i], x);
    if (nom[x] > 0) order.pb(nom[x] - 1);
}

int main()
{
    int n;
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        a[--x].pb(--y);
        a[y].pb(x);
    }
    for (int i = 0; i < k; i++) cin >> pos[i], pos[i]--;
    for (int i = 0; i < k; i++)
    {
        dist[i].resize(n);
        Calc_Dist(pos[i], -1, 0, i);
    }

    for (int i = 0; i < n; i++)
    {
        int mx = n;
        for (int j = 0; j < k; j++) mx = min(mx, dist[j][i]);
        for (int j = 0; j < k; j++)
            if (dist[j][i] == mx) kol[i]++, nearest[j].pb(i), nearest_sheep[i].pb(j);
    }

    for (int i = 0; i < k; i++) nom[pos[i]] = i + 1;
    Calc_Order(0, 0);

    vector <int> ans;
    bool mrk[k];
    for (int i = 0; i < k; i++) mrk[i] = 0;
    for (int c = 0; c < k; c++)
    {
        int x = order[c];
        if (mrk[x]) continue;
        int mx = 0, nom = -1;
        for (int i = 0; i < nearest[x].size(); i++)
            if (kol[nearest[x][i]] > mx) mx = kol[nearest[x][i]], nom = nearest[x][i];
        if (nom == -1) continue;
        for (int i = 0; i < nearest_sheep[nom].size(); i++) Delete_Sheep(nearest_sheep[nom][i]);
        ans.pb(nom + 1);
    }
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
}

Compilation message

pastiri.cpp: In function 'void Calc_Dist(int, int, int, int)':
pastiri.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0; i < a[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~
pastiri.cpp: In function 'void Delete_Sheep(int)':
pastiri.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i = 0; i < nearest[x].size(); i++) kol[nearest[x][i]]--;
      |                     ~~^~~~~~~~~~~~~~~~~~~
pastiri.cpp: In function 'void Calc_Order(int, int)':
pastiri.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < a[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~
pastiri.cpp: In function 'int main()':
pastiri.cpp:85:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for (int i = 0; i < nearest[x].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~~~~~
pastiri.cpp:88:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for (int i = 0; i < nearest_sheep[nom].size(); i++) Delete_Sheep(nearest_sheep[nom][i]);
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
pastiri.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
      |                     ~~^~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 162780 KB Output is correct
2 Execution timed out 1099 ms 228548 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 94956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 95980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 120440 KB Time limit exceeded
2 Halted 0 ms 0 KB -