oj.uz

답안 #845118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
845118 2023-09-06T12:01:38 Z vjudge1 Birmingham (COCI20_birmingham) C++17
70 / 70
 233 ms 8828 KB 
#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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 #8
5.0 / 5.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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