Submission #845163

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
845163	2023-09-06T12:22:35 Z	vjudge1	Birmingham (COCI20_birmingham)	C++17	70 / 70	93 ms	10996 KB

birmingham

// 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

#	Verdict	Execution time	Memory	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

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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

Submission #845163

Compilation message