oj.uz

Submission #581356

# Submission time Handle Problem Language Result Execution time Memory
581356 2022-06-22T14:06:57 Z WongChun1234 From Hacks to Snitches (BOI21_watchmen) C++14
5 / 100
 180 ms 39168 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=250050;
int n,m,u,v,k,l[N];
ll ans;
pair<int,int> incyc[N];
vector<int> adj[N],cyc[N];
vector<ll> dist[N];
vector<bool> final[N];
priority_queue<pair<ll,pair<int,int>>> dij;
int main(){
	cin>>n>>m;
	for (int i=1;i<=n;i++) incyc[i]={-1,-1},dist[i].resize(1),final[i].resize(1);
	for (int i=1;i<=m;i++){
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	cin>>k;
	for (int i=1;i<=k;i++){
		cin>>l[i];
		cyc[i].resize(l[i]);
		for (int j=0;j<l[i];j++){
			cin>>cyc[i][j];
			dist[cyc[i][j]].resize(l[i]);
			final[cyc[i][j]].resize(l[i]);
			incyc[cyc[i][j]]={i,j};
		}
	}
	for (int i=1;i<=n;i++) for (auto &j:dist[i]) j=1e16;
	dist[1][0]=0;
	dij.push({0,{1,0}});
	while (dij.size()){
		pair<int,int> cnde=dij.top().second;
		dij.pop();
		if (final[cnde.first][cnde.second]) continue;
		//cerr<<cnde.first<<","<<cnde.second<<":"<<dist[cnde.first][cnde.second]<<endl;
		final[cnde.first][cnde.second]=1;
		for (auto i:adj[cnde.first]){
			if (incyc[i].first==-1){
				if (dist[i][0]>dist[cnde.first][cnde.second]+1){
					dist[i][0]=dist[cnde.first][cnde.second]+1;
					dij.push({-dist[i][0],{i,0}});
				}
			}else if (incyc[cnde.first].first==-1){
				//no cyc -> cyc
				for (int j=(dist[cnde.first][cnde.second]+1)%l[incyc[i].first];j<l[incyc[i].first];j++){
					if (j==incyc[i].second) continue;
					if (dist[i][j]>dist[cnde.first][cnde.second]+1+j-(dist[cnde.first][cnde.second]+1)%l[incyc[i].first]){
						dist[i][j]=dist[cnde.first][cnde.second]+1+j-(dist[cnde.first][cnde.second]+1)%l[incyc[i].first];
						dij.push({-dist[i][j],{i,j}});
					}
				}
				ll ndadd=l[incyc[i].first]-(dist[cnde.first][cnde.second]+1)%l[incyc[i].first];
				for (int j=0;j<(dist[cnde.first][cnde.second]+1)%l[incyc[i].first];j++){
					if (j==incyc[i].second) continue;
					if (dist[i][j]>dist[cnde.first][cnde.second]+j+ndadd){
						dist[i][j]=dist[cnde.first][cnde.second]+j+ndadd;
						dij.push({-dist[i][j],{i,j}});
					}
				}
			}else{
				//cyc -> cyc
				if ((dist[cnde.first][cnde.second]+1)%l[incyc[i].first]==incyc[i].second) continue;
				//cerr<<((dist[cnde.first][cnde.second])%l[incyc[i].first]==incyc[i].second)<<";"<<((incyc[i].second+1)%l[incyc[i].first]==incyc[cnde.first].second)<<"\n";
				if ((dist[cnde.first][cnde.second])%l[incyc[i].first]==incyc[i].second&&(incyc[i].second+1)%l[incyc[i].first]==incyc[cnde.first].second) continue;
				if (dist[i][(cnde.second+1)%l[incyc[i].first]]>dist[cnde.first][cnde.second]+1){
					dist[i][(cnde.second+1)%l[incyc[i].first]]=dist[cnde.first][cnde.second]+1;
					dij.push({-dist[i][(cnde.second+1)%l[incyc[i].first]],{i,(cnde.second+1)%l[incyc[i].first]}});
				}
			}
		}
	}
	ans=LLONG_MAX;
	for (auto i:dist[n]) ans=min(ans,i);
	cout<<ans<<"\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 29644 KB Output is correct
2 Correct 146 ms 39168 KB Output is correct
3 Correct 135 ms 38436 KB Output is correct
4 Correct 180 ms 38908 KB Output is correct
5 Correct 21 ms 27740 KB Output is correct
6 Correct 137 ms 38464 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 29600 KB Output is correct
2 Correct 163 ms 39168 KB Output is correct
3 Correct 165 ms 38468 KB Output is correct
4 Correct 164 ms 38924 KB Output is correct
5 Correct 17 ms 27888 KB Output is correct
6 Correct 139 ms 38528 KB Output is correct
7 Correct 177 ms 38292 KB Output is correct
8 Correct 152 ms 38216 KB Output is correct
9 Incorrect 123 ms 38216 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 29600 KB Output is correct
2 Correct 163 ms 39168 KB Output is correct
3 Correct 165 ms 38468 KB Output is correct
4 Correct 164 ms 38924 KB Output is correct
5 Correct 17 ms 27888 KB Output is correct
6 Correct 139 ms 38528 KB Output is correct
7 Correct 177 ms 38292 KB Output is correct
8 Correct 152 ms 38216 KB Output is correct
9 Incorrect 123 ms 38216 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 29600 KB Output is correct
2 Correct 163 ms 39168 KB Output is correct
3 Correct 165 ms 38468 KB Output is correct
4 Correct 164 ms 38924 KB Output is correct
5 Correct 17 ms 27888 KB Output is correct
6 Correct 139 ms 38528 KB Output is correct
7 Correct 177 ms 38292 KB Output is correct
8 Correct 152 ms 38216 KB Output is correct
9 Incorrect 123 ms 38216 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 29644 KB Output is correct
2 Correct 146 ms 39168 KB Output is correct
3 Correct 135 ms 38436 KB Output is correct
4 Correct 180 ms 38908 KB Output is correct
5 Correct 21 ms 27740 KB Output is correct
6 Correct 137 ms 38464 KB Output is correct
7 Correct 105 ms 29600 KB Output is correct
8 Correct 163 ms 39168 KB Output is correct
9 Correct 165 ms 38468 KB Output is correct
10 Correct 164 ms 38924 KB Output is correct
11 Correct 17 ms 27888 KB Output is correct
12 Correct 139 ms 38528 KB Output is correct
13 Correct 177 ms 38292 KB Output is correct
14 Correct 152 ms 38216 KB Output is correct
15 Incorrect 123 ms 38216 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 29644 KB Output is correct
2 Correct 146 ms 39168 KB Output is correct
3 Correct 135 ms 38436 KB Output is correct
4 Correct 180 ms 38908 KB Output is correct
5 Correct 21 ms 27740 KB Output is correct
6 Correct 137 ms 38464 KB Output is correct
7 Correct 105 ms 29600 KB Output is correct
8 Correct 163 ms 39168 KB Output is correct
9 Correct 165 ms 38468 KB Output is correct
10 Correct 164 ms 38924 KB Output is correct
11 Correct 17 ms 27888 KB Output is correct
12 Correct 139 ms 38528 KB Output is correct
13 Correct 177 ms 38292 KB Output is correct
14 Correct 152 ms 38216 KB Output is correct
15 Incorrect 123 ms 38216 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 29644 KB Output is correct
2 Correct 146 ms 39168 KB Output is correct
3 Correct 135 ms 38436 KB Output is correct
4 Correct 180 ms 38908 KB Output is correct
5 Correct 21 ms 27740 KB Output is correct
6 Correct 137 ms 38464 KB Output is correct
7 Correct 105 ms 29600 KB Output is correct
8 Correct 163 ms 39168 KB Output is correct
9 Correct 165 ms 38468 KB Output is correct
10 Correct 164 ms 38924 KB Output is correct
11 Correct 17 ms 27888 KB Output is correct
12 Correct 139 ms 38528 KB Output is correct
13 Correct 177 ms 38292 KB Output is correct
14 Correct 152 ms 38216 KB Output is correct
15 Incorrect 123 ms 38216 KB Output isn't correct
16 Halted 0 ms 0 KB -