oj.uz

Submission #381579

# Submission time Handle Problem Language Result Execution time Memory
381579 2021-03-25T10:23:17 Z topovik Pastiri (COI20_pastiri) C++14
0 / 100
 1000 ms 234484 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];
bool mrk[N];
int kol[N];
int pos[N];
int depth[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)
{
    mrk[x] = 1;
    for (int i = 0; i < nearest[x].size(); i++) kol[nearest[x][i]]--;
}

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 mn = n;
        for (int j = 0; j < k; j++) mn = min(mn, dist[j][i]);
        for (int j = 0; j < k; j++)
            if (dist[j][i] == mn) nearest[j].pb(i), kol[i]++, nearest_sheep[i].pb(j);
    }

//    for (int j = 0; j < k; j++)
//    {
//        for (int i = 0; i < n; i++) cout << dist[j][i] << " ";
//        cout << endl;
//    }
//    Calc_Depth(0, 0, 0);

    for (int i = 0; i < k; i++) mrk[i] = 0;
    vector <int> ans;
    while (1)
    {
        int mx = 0, nom = -1;
        for (int j = 0; j < n; j++)
            if (kol[j] > mx) mx = kol[j], nom = j;
        if (nom == -1) break;
        ans.pb(nom + 1);
        for (int j = 0; j < nearest_sheep[nom].size(); j++)
            if (!mrk[nearest_sheep[nom][j]]) Delete_Sheep(nearest_sheep[nom][j]);
    }
    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:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i < a[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~
pastiri.cpp: In function 'void Delete_Sheep(int)':
pastiri.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 0; i < nearest[x].size(); i++) kol[nearest[x][i]]--;
      |                     ~~^~~~~~~~~~~~~~~~~~~
pastiri.cpp: In function 'int main()':
pastiri.cpp:81:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (int j = 0; j < nearest_sheep[nom].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
pastiri.cpp:85:23: 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 < ans.size(); i++) cout << ans[i] << " ";
      |                     ~~^~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 156868 KB Output is correct
2 Execution timed out 1112 ms 234484 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 94956 KB Output is correct
2 Correct 63 ms 94956 KB Output is correct
3 Execution timed out 1092 ms 125676 KB Time limit exceeded
4 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 1104 ms 122356 KB Time limit exceeded
2 Halted 0 ms 0 KB -