oj.uz

답안 #845163

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
845163 2023-09-06T12:22:35 Z vjudge1 Birmingham (COCI20_birmingham) C++17
70 / 70
 93 ms 10996 KB 
// Imagine not FFT
#include <bits/stdc++.h>
#define ONLINE_JUDGE
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
 
#ifndef ONLINE_JUDGE
    #define DEBUG(x) std::cerr << #x << ": " << x << std::endl;
    #define DEBUGV(x) std::cerr << #x << ": { "; for(auto ___y:x) std::cerr << ___y << " "; std::cerr << "}" << std::endl;
    #define DEBUGVV(x) std::cerr << #x << ": { \n"; for(int _i=0;_i<sz(x);++_i) {DEBUGV(x[_i]);} std::cerr << "}" << std::endl;
	#define DEBUGVP(x) std::cerr << #x << ": { "; for(auto ___y:x) std::cerr << "{" << ___y.first << "," << ___y.second << "}" << " "; std::cerr << "}" << std::endl;
	#define files freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
    #define fastio std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr);
#else
    #define fastio std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr);
    #define DEBUG(...) void(23)
    #define DEBUGV(x) void(23);
    #define DEBUGARR(arr, size) void(23)
    #define DEBUGPRINT(...) void(23)
    #define DEBUGMAP(...) void(23)
    #define DEBUGMAPQUEUE(...) void(23)
    #define DEBUGVV(x) void(23);
    #define DEBUGVP(x) void(23);
    #define files void(23);
#endif

#define int long long
#define ll long long
 
#define pb push_back
#define ff first
#define ss second
#define pii std::pair < int , int >
#define pll std::pair < ll , ll >
#define vi std::vector < ll >
#define vl std::vector < int >
#define vii std::vector < pii >
#define vll std::vector < pll >
#define vvi std::vector < vi >
#define vvii std::vector < vii >
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define forn(i,j) for(int i=0;i<j;i++)
#define forr(i,j,k) for(int i=j;i<k;i++)
 
#define mset multiset
#define pqueue priority_queue
#define cmax(a,b) (a = max(a,b))
#define cmin(a,b) (a = min(a,b))
 
#define sz(a) (int)(a.size())
     
const int MOD = 1000000007;
const int MOD2 = 998244353;

using namespace std;

void solve(int _t_case){
	int n,m,qq,k;
	cin >> n >> m >> qq >> k;
	queue < pair < int , int > > q;
	vi val(n+2,-1);
	while(qq--){
		int x;
		cin >> x;
		q.push({0,x});
		val[x]=0;
	}
	vvi b(n+2);
	DEBUGVV(b);
	forn(i,m){
		int u,v;
		cin >> u >> v;
		b[u].pb(v);
		b[v].pb(u);
	}
	int day=0,last=0;
	while(!q.empty()){
		int c=q.front().ff;
		int d=q.front().ss;
		q.pop();
		if(c-last==k*day){
			last=c;
			++day;
		}
//		val[d]=day;
		for(auto e:b[d]) if(val[e]==-1) {
			val[e]=day;q.push({c+1,e});
		}
		DEBUG(d);
		DEBUG(k);
		DEBUG(c);
		DEBUG(day);
	}
	forn(i,n){
		cout << val[i+1] << " ";
	}

	return;
}

signed main(){
    fastio;
    files;
    int t=1,_t=0;
//    std::cin >> t;
    while(_t<t){
        ++_t;
        solve(_t);
    }
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
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 #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 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 348 KB Output is correct

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 10028 KB Output is correct
2 Correct 67 ms 10532 KB Output is correct
3 Correct 86 ms 10876 KB Output is correct
4 Correct 50 ms 9420 KB Output is correct
5 Correct 60 ms 9676 KB Output is correct
6 Correct 67 ms 10996 KB Output is correct

Subtask #9
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 10620 KB Output is correct
2 Correct 93 ms 10388 KB Output is correct
3 Correct 91 ms 10580 KB Output is correct
4 Correct 63 ms 10908 KB Output is correct
5 Correct 66 ms 10388 KB Output is correct
6 Correct 61 ms 10268 KB Output is correct

Subtask #10
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 10268 KB Output is correct
2 Correct 70 ms 10724 KB Output is correct
3 Correct 64 ms 10700 KB Output is correct
4 Correct 80 ms 10544 KB Output is correct
5 Correct 74 ms 10004 KB Output is correct
6 Correct 72 ms 10352 KB Output is correct

Subtask #11
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 9812 KB Output is correct
2 Correct 78 ms 10460 KB Output is correct
3 Correct 61 ms 10640 KB Output is correct
4 Correct 54 ms 10028 KB Output is correct
5 Correct 58 ms 9604 KB Output is correct
6 Correct 51 ms 10308 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 9884 KB Output is correct
2 Correct 53 ms 10028 KB Output is correct
3 Correct 54 ms 10140 KB Output is correct
4 Correct 63 ms 10028 KB Output is correct
5 Correct 76 ms 9992 KB Output is correct
6 Correct 54 ms 10000 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 9912 KB Output is correct
2 Correct 52 ms 10064 KB Output is correct
3 Correct 51 ms 10064 KB Output is correct
4 Correct 69 ms 10316 KB Output is correct
5 Correct 53 ms 10036 KB Output is correct
6 Correct 63 ms 10276 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 10012 KB Output is correct
2 Correct 58 ms 9500 KB Output is correct
3 Correct 60 ms 10832 KB Output is correct
4 Correct 58 ms 10040 KB Output is correct
5 Correct 62 ms 10468 KB Output is correct
6 Correct 59 ms 10832 KB Output is correct