oj.uz

답안 #238420

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
238420 2020-06-11T07:39:28 Z MishoKostov Birmingham (COCI20_birmingham) C++14
15 / 70
 110 ms 10712 KB 
#include<bits/stdc++.h>
#define endl "\n"

using namespace std;

struct edge
{
    int x, time;
    edge() { }
    edge(int x, int time) :x(x), time(time) { }
};

const int nmax=200010;
int n, m, qr, k;
vector<int> g;
vector<int> v[nmax];
int ans[nmax];

void bfs()
{
    bool used[nmax];
    memset(used, 0, sizeof(used));
    queue<edge> q;
    for(int i=0; i<qr; ++i) q.push(edge(g[i], 0)), used[g[i]]=true;
    while(!q.empty())
    {
        edge w=q.front();
        q.pop();
        //used[w.x]=true;
        ans[w.x]=w.time%k ? w.time/k+1 : w.time/k;
        for(int i=0; i<v[w.x].size(); ++i)
        {
            int nb=v[w.x][i];
            if(!used[nb]) q.push(edge(nb, w.time+1)), used[nb]=true;
        }
    }
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int x, y;
	cin>>n>>m>>qr>>k;
	for(int i=0; i<qr; ++i) cin>>x, g.push_back(x);
	for(int i=0; i<m; ++i)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    bfs();
    for(int i=1; i<=n; ++i) cout<<ans[i]<<" ";
    cout<<endl;
	return 0;
}

Compilation message

birmingham.cpp: In function 'void bfs()':
birmingham.cpp:31:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<v[w.x].size(); ++i)
                      ~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 5248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 5248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 5248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 5248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 93 ms 10360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 107 ms 10580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 100 ms 10428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 91 ms 10204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 10200 KB Output is correct
2 Incorrect 103 ms 10712 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 88 ms 10232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 110 ms 10292 KB Output isn't correct
2 Halted 0 ms 0 KB -