oj.uz

답안 #238449

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
238449 2020-06-11T11:26:42 Z vankata Birmingham (COCI20_birmingham) C++14
70 / 70
 250 ms 12040 KB 
#include<bits/stdc++.h>
using namespace std;
const int  MAXN = (int )(1<<17);
vector<long long >v[MAXN];
vector <long long > rig;
long long  n,m,q,k,used[MAXN];
void BFS()
{
    long long  i,j;
    queue<long long >q;
    for(auto nb:rig)
    {
        used[nb]=true;
        q.push(nb);
    }
    while(!q.empty())
    {
        i=q.front();
        q.pop();
        for(auto nb:v[i])
        {
            if(!used[nb])
            {
                used[nb]=used[i]+1;
                q.push(nb);
            }
        }
    }
}
void read()
{
    long long  i,j,x,y;
    cin>>n>>m>>q>>k;
    for(i=0;i<q;i++)
    {
        cin>>x;
        rig.push_back(x);
    }
    for(i=0;i<m;i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}
void solve()
{
    long long  i,ans=0;
    for(i=1;i<=n;i++)
    {
        used[i]--;
        ans= used[i]/k;
        if(used[i]%k)ans++;
        ans*=2;
        used[i]=sqrt(ans);
        if(used[i]*(used[i]+1)<ans)used[i]++;
        cout<<used[i]<<" ";
    }cout<<endl;
}
int main()
{
    read();
    BFS();
    solve();
    return 0;
}

Compilation message

birmingham.cpp: In function 'void BFS()':
birmingham.cpp:9:18: warning: unused variable 'j' [-Wunused-variable]
     long long  i,j;
                  ^
birmingham.cpp: In function 'void read()':
birmingham.cpp:32:18: warning: unused variable 'j' [-Wunused-variable]
     long long  i,j,x,y;
                  ^

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 6 ms 3456 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 7 ms 3456 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 7 ms 3456 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 6 ms 3456 KB Output is correct

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 10488 KB Output is correct
2 Correct 229 ms 10792 KB Output is correct
3 Correct 249 ms 11376 KB Output is correct
4 Correct 192 ms 9832 KB Output is correct
5 Correct 194 ms 10072 KB Output is correct
6 Correct 246 ms 12008 KB Output is correct

Subtask #9
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 236 ms 10868 KB Output is correct
2 Correct 221 ms 10672 KB Output is correct
3 Correct 234 ms 10992 KB Output is correct
4 Correct 236 ms 11044 KB Output is correct
5 Correct 221 ms 10676 KB Output is correct
6 Correct 220 ms 11340 KB Output is correct

Subtask #10
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 215 ms 10616 KB Output is correct
2 Correct 250 ms 10916 KB Output is correct
3 Correct 247 ms 11448 KB Output is correct
4 Correct 239 ms 10916 KB Output is correct
5 Correct 203 ms 10232 KB Output is correct
6 Correct 222 ms 11368 KB Output is correct

Subtask #11
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 199 ms 9976 KB Output is correct
2 Correct 221 ms 10616 KB Output is correct
3 Correct 243 ms 11284 KB Output is correct
4 Correct 212 ms 10360 KB Output is correct
5 Correct 190 ms 9976 KB Output is correct
6 Correct 212 ms 11244 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 200 ms 10068 KB Output is correct
2 Correct 209 ms 10424 KB Output is correct
3 Correct 216 ms 10484 KB Output is correct
4 Correct 202 ms 10360 KB Output is correct
5 Correct 208 ms 10308 KB Output is correct
6 Correct 219 ms 11348 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 204 ms 10072 KB Output is correct
2 Correct 207 ms 10428 KB Output is correct
3 Correct 213 ms 10812 KB Output is correct
4 Correct 229 ms 10744 KB Output is correct
5 Correct 202 ms 10192 KB Output is correct
6 Correct 218 ms 11500 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 202 ms 10360 KB Output is correct
2 Correct 189 ms 9848 KB Output is correct
3 Correct 248 ms 11352 KB Output is correct
4 Correct 199 ms 10168 KB Output is correct
5 Correct 220 ms 10488 KB Output is correct
6 Correct 250 ms 12040 KB Output is correct