oj.uz

Submission #219323

# Submission time Handle Problem Language Result Execution time Memory
219323 2020-04-05T06:52:35 Z Vimmer Birmingham (COCI20_birmingham) C++14
70 / 70
 112 ms 8152 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define F first
#define S second
#define sz(x) ll(x.size())
#define pb push_back
#define N 100005
#define M ll(998244353)

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef short int si;

//typedef tree<int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> oredered_set;


vector <int> g[N];

int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m, q, k;

    cin >> n >> m >> q >> k;

    vector <int> gr(q);

    for (int i = 0; i < q; i++) cin >> gr[i];

    for (int i = 0; i < m; i++)
    {
        int a, b;

        cin >> a >> b;

        g[a].pb(b);

        g[b].pb(a);
    }

    int ans[n + 1], kol = q;

    for (int i = 1; i <= n; i++) ans[i] = -1;

    for (auto it : gr) ans[it] = 0;

    int day = 1;

    while (kol < n)
    {
        vector <int> vr; vr.clear();

        for (int i = 0; i < day * k && kol < n; i++)
        {
            for (auto it : gr)
             {
              if (kol == n) break;

              for (auto itr : g[it])
              {
                  if (kol == n) break;

                  if (ans[itr] != -1) continue;

                  ans[itr] = day;

                  kol++;

                  vr.pb(itr);
              }
            }

            gr = vr;

            vr.clear();
        }

        day++;
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 7 ms 2688 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 7 ms 2816 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 7548 KB Output is correct
2 Correct 112 ms 7764 KB Output is correct
3 Correct 105 ms 7948 KB Output is correct
4 Correct 77 ms 7464 KB Output is correct
5 Correct 82 ms 7488 KB Output is correct
6 Correct 97 ms 7836 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 8036 KB Output is correct
2 Correct 92 ms 7800 KB Output is correct
3 Correct 98 ms 7924 KB Output is correct
4 Correct 95 ms 7928 KB Output is correct
5 Correct 92 ms 7784 KB Output is correct
6 Correct 88 ms 7468 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 7672 KB Output is correct
2 Correct 100 ms 7900 KB Output is correct
3 Correct 101 ms 7952 KB Output is correct
4 Correct 111 ms 8152 KB Output is correct
5 Correct 88 ms 7544 KB Output is correct
6 Correct 88 ms 7456 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 7420 KB Output is correct
2 Correct 89 ms 7780 KB Output is correct
3 Correct 100 ms 7924 KB Output is correct
4 Correct 86 ms 7544 KB Output is correct
5 Correct 80 ms 7396 KB Output is correct
6 Correct 85 ms 7452 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 7416 KB Output is correct
2 Correct 88 ms 7648 KB Output is correct
3 Correct 109 ms 7668 KB Output is correct
4 Correct 89 ms 7544 KB Output is correct
5 Correct 92 ms 7596 KB Output is correct
6 Correct 82 ms 7452 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 7544 KB Output is correct
2 Correct 92 ms 7648 KB Output is correct
3 Correct 86 ms 7416 KB Output is correct
4 Correct 109 ms 7940 KB Output is correct
5 Correct 86 ms 7552 KB Output is correct
6 Correct 104 ms 7456 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 7672 KB Output is correct
2 Correct 80 ms 7288 KB Output is correct
3 Correct 103 ms 8008 KB Output is correct
4 Correct 90 ms 7544 KB Output is correct
5 Correct 91 ms 7652 KB Output is correct
6 Correct 99 ms 7836 KB Output is correct