Submission #845118

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
845118	2023-09-06T12:01:38 Z	vjudge1	Birmingham (COCI20_birmingham)	C++17	70 / 70	233 ms	8828 KB

birmingham

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
#define pb push_back
#define CDIV(a,b) (((a)+(b)-(1))/(b))

 
int mod_(int a, int b)
{
    if(a >= 0)return a % b;
    a += (-a/b + 1) * b;
    return a % b;
}

int k;
ll c(ll x)
{
    return k * x * (x + 1) / 2;
}

ll calc(ll x)
{
    int l = 1, r = 10;
    while(l <= r)
    {
        int m = (l + r)/2;
        if(c(m) >= x)r = m - 1;
        else l = m + 1;
    }
    return l;

}

void solve()
{
    int n, m, f;
    cin >> n >> m >> f >> k;
    vector<int> g[n + 1];
    vector<int>dist(n + 1, INT32_MAX);
    queue<array<int, 2> >q;
    vector<bool>vis(n + 1);

    while(f--)
    {
        int u;
        cin >> u;
        q.push({u, 0});
    }

    for(int i = 0; i < m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    while(!q.empty())
    {
        int node = q.front()[0], d = q.front()[1];
        //cerr << node << endl;
        q.pop();
        dist[node] = min(d, dist[node]);
        if(vis[node])continue;
        vis[node] = true;

        for(int next : g[node])
        {
            if(!vis[next])
                q.push({next, d + 1});
        }
    }

    for(int i = 1; i <= n; ++i)
    {
        if(dist[i])
        {
            //cout << i << ' ' << dist[i] << ' ';
            cout <<  calc(dist[i]) << endl;
        }
        else cout << 0 << endl;
    }

}
    

int main()
{
    //fio;
    //int t; cin >> t; while(t--)
    {
        solve();
    }
}

Subtask #1
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	600 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	496 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	344 KB	Output is correct
3	Correct	344 KB	Output is correct
4	Correct	344 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	207 ms	7876 KB	Output is correct
2	Correct	233 ms	8608 KB	Output is correct
3	Correct	228 ms	8784 KB	Output is correct
4	Correct	197 ms	7504 KB	Output is correct
5	Correct	202 ms	7560 KB	Output is correct
6	Correct	225 ms	8784 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	221 ms	8176 KB	Output is correct
2	Correct	227 ms	7936 KB	Output is correct
3	Correct	222 ms	8272 KB	Output is correct
4	Correct	229 ms	8272 KB	Output is correct
5	Correct	215 ms	7932 KB	Output is correct
6	Correct	218 ms	8176 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	209 ms	7992 KB	Output is correct
2	Correct	220 ms	8528 KB	Output is correct
3	Correct	227 ms	8528 KB	Output is correct
4	Correct	229 ms	8216 KB	Output is correct
5	Correct	206 ms	7760 KB	Output is correct
6	Correct	225 ms	8204 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	203 ms	7504 KB	Output is correct
2	Correct	220 ms	8092 KB	Output is correct
3	Correct	224 ms	8272 KB	Output is correct
4	Correct	205 ms	7760 KB	Output is correct
5	Correct	204 ms	7536 KB	Output is correct
6	Correct	212 ms	8036 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	205 ms	8012 KB	Output is correct
2	Correct	209 ms	7968 KB	Output is correct
3	Correct	219 ms	8272 KB	Output is correct
4	Correct	209 ms	7716 KB	Output is correct
5	Correct	214 ms	8268 KB	Output is correct
6	Correct	210 ms	8016 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	207 ms	7940 KB	Output is correct
2	Correct	211 ms	7760 KB	Output is correct
3	Correct	217 ms	8192 KB	Output is correct
4	Correct	216 ms	7948 KB	Output is correct
5	Correct	220 ms	7760 KB	Output is correct
6	Correct	212 ms	8048 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	211 ms	7808 KB	Output is correct
2	Correct	208 ms	7504 KB	Output is correct
3	Correct	230 ms	8436 KB	Output is correct
4	Correct	211 ms	7760 KB	Output is correct
5	Correct	211 ms	7996 KB	Output is correct
6	Correct	226 ms	8828 KB	Output is correct

Submission #845118

Compilation message