oj.uz

Submission #406117

# Submission time Handle Problem Language Result Execution time Memory
406117 2021-05-17T08:36:10 Z oolimry From Hacks to Snitches (BOI21_watchmen) C++17
0 / 100
 1437 ms 31300 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
#define show3(x, y, z) cerr << #x << " is " << x << ", " << #y << " is " << y << ", " << #z << " is " << z << endl;
#define l first
#define r second
typedef long long lint;
typedef pair<int, int> ii;

int mod[250005];
int rem[250005];
int label[250005];

vector<int> dis[250005];
vector<int> adj[250005];

vector<ii> Q[500005];
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	//freopen("i.txt","r",stdin);
	
	int n, m; cin >> n >> m;
	for(int i = 1;i <= m;i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	for(int i = 1;i <= n;i++) mod[i] = 1, rem[i] = 1;
	int K; cin >> K;
	for(int i = 1;i <= K;i++){
		int L; cin >> L;
		for(int u = 0;u < L;u++){
			int x; cin >> x;
			mod[x] = L;
			rem[x] = u;
			label[x] = i;
		}
	}
	
	const int inf = 102345678;
	for(int i = 1;i <= n;i++){
		dis[i].resize(mod[i]);
		fill(all(dis[i]), inf);
	}

	Q[0].push_back(ii(1,0));
	for(int d = 0;d <= 4000;d++){
		for(ii u : Q[d]){
			 int a = u.first, b = u.second;
			 if(d % mod[a] == rem[a]) continue;
			// show3(a,b,d);
			 dis[a][b] = d;
			 for(int v : adj[a]){
				 for(int r = 1;r <= mod[v];r++){
					 if((d+r)%mod[a] == rem[a]){
						 if(rem[v] == (rem[a]+1)%mod[v] or label[a] != label[v]){
							int rr = (d+r)%mod[v];
							if(dis[v][rr] > d+r){
								dis[v][rr] = d+r;
								Q[d+r].push_back(ii(v, (d+r)%mod[v]));
							}
						 }
						 break;
					 }
					int rr = (d+r)%mod[v];
					if(dis[v][rr] > d+r){
						dis[v][rr] = d+r;
						Q[d+r].push_back(ii(v, (d+r)%mod[v]));
					}
				 }
			 }
		}
		Q[d].clear();
	}
	
	cout << dis[n][0];
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1426 ms 24856 KB Output is correct
2 Incorrect 58 ms 31232 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1437 ms 24852 KB Output is correct
2 Incorrect 62 ms 31300 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1437 ms 24852 KB Output is correct
2 Incorrect 62 ms 31300 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1437 ms 24852 KB Output is correct
2 Incorrect 62 ms 31300 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1426 ms 24856 KB Output is correct
2 Incorrect 58 ms 31232 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1426 ms 24856 KB Output is correct
2 Incorrect 58 ms 31232 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1426 ms 24856 KB Output is correct
2 Incorrect 58 ms 31232 KB Output isn't correct
3 Halted 0 ms 0 KB -