Submission #947846

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
947846	2024-03-17T06:28:33 Z	willychan	From Hacks to Snitches (BOI21_watchmen)	C++17	5 / 100	440 ms	8464 KB

watchmen

#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){
	x%=l;
	return (n*x+c);
}


int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	vector<vector<int>> side(n);
	for(int i=0;i<m;i++){
		int a,b;cin>>a>>b;
		a--;
		b--;
		side[a].push_back(b);
		side[b].push_back(a);
	}
	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];
	for(int i=0;i<l;i++) node[i]--;

	vector<bool> vis(n*l);
	for(int i=0;i<l;i++){
		vis[mp(node[i],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;
		}
		int u = cur.first%n;
		int t = cur.first/n;
		if(!vis[mp(u,t+1)]){
			vis[mp(u,t+1)]=1;
			q.push({mp(u,t+1),cur.second+1});
		}
		for(auto i : side[u]){
			if(node[t]==i && node[(t+1)%l]==u) continue;
			if(!vis[mp(i,t+1)]){
				vis[mp(i,t+1)]=1;
				q.push({mp(i,t+1),cur.second+1});
			}
		}
	}
	cout<<"impossible\n";

	return 0;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1368 KB	Output is correct
2	Correct	316 ms	7468 KB	Output is correct
3	Correct	378 ms	8180 KB	Output is correct
4	Correct	390 ms	8284 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	389 ms	8320 KB	Output is correct

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1368 KB	Output is correct
2	Correct	323 ms	7452 KB	Output is correct
3	Correct	372 ms	8140 KB	Output is correct
4	Correct	394 ms	8464 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	440 ms	8240 KB	Output is correct
7	Incorrect	22 ms	6568 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1368 KB	Output is correct
2	Correct	323 ms	7452 KB	Output is correct
3	Correct	372 ms	8140 KB	Output is correct
4	Correct	394 ms	8464 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	440 ms	8240 KB	Output is correct
7	Incorrect	22 ms	6568 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #4

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1368 KB	Output is correct
2	Correct	323 ms	7452 KB	Output is correct
3	Correct	372 ms	8140 KB	Output is correct
4	Correct	394 ms	8464 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	440 ms	8240 KB	Output is correct
7	Incorrect	22 ms	6568 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #5

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1368 KB	Output is correct
2	Correct	316 ms	7468 KB	Output is correct
3	Correct	378 ms	8180 KB	Output is correct
4	Correct	390 ms	8284 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	389 ms	8320 KB	Output is correct
7	Correct	9 ms	1368 KB	Output is correct
8	Correct	323 ms	7452 KB	Output is correct
9	Correct	372 ms	8140 KB	Output is correct
10	Correct	394 ms	8464 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	440 ms	8240 KB	Output is correct
13	Incorrect	22 ms	6568 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #6

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1368 KB	Output is correct
2	Correct	316 ms	7468 KB	Output is correct
3	Correct	378 ms	8180 KB	Output is correct
4	Correct	390 ms	8284 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	389 ms	8320 KB	Output is correct
7	Correct	9 ms	1368 KB	Output is correct
8	Correct	323 ms	7452 KB	Output is correct
9	Correct	372 ms	8140 KB	Output is correct
10	Correct	394 ms	8464 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	440 ms	8240 KB	Output is correct
13	Incorrect	22 ms	6568 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #7

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1368 KB	Output is correct
2	Correct	316 ms	7468 KB	Output is correct
3	Correct	378 ms	8180 KB	Output is correct
4	Correct	390 ms	8284 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	389 ms	8320 KB	Output is correct
7	Correct	9 ms	1368 KB	Output is correct
8	Correct	323 ms	7452 KB	Output is correct
9	Correct	372 ms	8140 KB	Output is correct
10	Correct	394 ms	8464 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	440 ms	8240 KB	Output is correct
13	Incorrect	22 ms	6568 KB	Output isn't correct
14	Halted	0 ms	0 KB	-