oj.uz

Submission #947843

# Submission time Handle Problem Language Result Execution time Memory
947843 2024-03-17T06:18:06 Z willychan From Hacks to Snitches (BOI21_watchmen) C++17
0 / 100
 1405 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
int l;
int n,m;
int mp(int c,int x){
	return (n*x+c);
}


int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	vector<pair<int,int> > e(m);
	for(int i=0;i<m;i++) cin>>e[i].first>>e[i].second;
	int k;cin>>k;
	if(k>1) return 0;
	cin>>l;
	vector<int> node(l);
	for(int i=0;i<l;i++) cin>>node[i];
	vector<vector<int> > side(n*l);
	for(int i=0;i<n;i++){
		for(int j=0;j<l;j++){
			side[mp(i,j)].push_back(mp(i,(j+1)%l));
		}
	}
	for(auto p : e){
		int a = p.first-1;
		int b = p.second-1;
		for(int j=0;j<l;j++){
			side[mp(a,j)].push_back(mp(b,(j+1)%l));
			side[mp(b,j)].push_back(mp(a,(j+1)%l));
		}
	}
	vector<bool> vis(n*l);
	for(int i=0;i<l;i++){
		vis[mp(node[i]-1,i)]=1;
	}
	queue<pair<int,int> > q;	
	q.push({mp(0,0),0});
	vis[0]=1;
	while(q.size())	{
		auto cur =q.front();
		q.pop();
		if((cur.first%n)==(n-1)){
			cout<<cur.second<<"\n";
			return 0;
		}
		for(auto i : side[cur.first]){
			if(!vis[i])	{
				vis[i]=1;
				q.push({i,cur.second+1});
			}
		}
	}
	cout<<"impossible\n";

	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 104932 KB Output is correct
2 Runtime error 1405 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 104936 KB Output is correct
2 Runtime error 407 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 104936 KB Output is correct
2 Runtime error 407 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 104936 KB Output is correct
2 Runtime error 407 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 104932 KB Output is correct
2 Runtime error 1405 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 104932 KB Output is correct
2 Runtime error 1405 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 104932 KB Output is correct
2 Runtime error 1405 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -