oj.uz

Submission #420636

# Submission time Handle Problem Language Result Execution time Memory
420636 2021-06-08T13:03:24 Z lakshith_ From Hacks to Snitches (BOI21_watchmen) C++14
5 / 100
 1811 ms 106344 KB 
#include <bits/stdc++.h>

using namespace std;

//#define int long long 
#define what_is(a) cout << #a << " is " <<a << "\n"
#define checker(a) cout << "chekcer reached " << a << "\n"

inline void io(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

vector<vector<int>> adj(1000000,vector<int>());

struct node{
	int n,t,a;
};

void print(node n){
	cout << n.n << " " << n.t << " " << n.a << "\n";
}

int mem[1000000][200];

void solve(){
	int n,m;
	cin >> n >> m;
	for(int i=0;i<m;i++){
		int u,v;
		cin >>u >> v;
		u--,v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	int k,l;
	cin >> k;
	assert(k==1);
	cin >> l;
	vector<int> w;
	for(int i=0;i<l;i++){
		int a;
		cin >> a;
		a--;
		w.push_back(a);
	}
		
	int ans = -1;
	queue<node> q;
	q.push({0,0,0});
	while(!q.empty()){
		node u = q.front();
		//print(u);
		q.pop();
		if(u.n==n-1){
			ans = u.a;
			break;
		}
		for(int v:adj[u.n]){
			if(w[(u.t+1)%l]==v)continue;
			if(w[(u.t+1)%l]==u.n&&w[(u.t)%l]==v)continue;
			if(mem[v][(u.t+1)%l])continue;
			mem[v][(u.t+1)%l] = 1;
			q.push({v,(u.t+1)%l,u.a+1});
		}
		if(w[(u.t+1)%l]!=u.n && mem[u.n][(u.t+1)%l]==0){
			q.push({u.n,(u.t+1)%l,u.a+1});
			mem[u.n][(u.t+1)%l] = 1;
		}
	}
	cout << (ans==-1?"impossible":to_string(ans)) << " \n";
}

signed main(){
	solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 25596 KB Output is correct
2 Correct 722 ms 106344 KB Output is correct
3 Correct 1126 ms 98624 KB Output is correct
4 Correct 1811 ms 99040 KB Output is correct
5 Correct 16 ms 23884 KB Output is correct
6 Correct 1367 ms 98612 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 25540 KB Output is correct
2 Correct 724 ms 106344 KB Output is correct
3 Correct 1053 ms 98684 KB Output is correct
4 Correct 1773 ms 99012 KB Output is correct
5 Correct 18 ms 23876 KB Output is correct
6 Correct 1240 ms 98792 KB Output is correct
7 Runtime error 145 ms 27768 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 25540 KB Output is correct
2 Correct 724 ms 106344 KB Output is correct
3 Correct 1053 ms 98684 KB Output is correct
4 Correct 1773 ms 99012 KB Output is correct
5 Correct 18 ms 23876 KB Output is correct
6 Correct 1240 ms 98792 KB Output is correct
7 Runtime error 145 ms 27768 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 25540 KB Output is correct
2 Correct 724 ms 106344 KB Output is correct
3 Correct 1053 ms 98684 KB Output is correct
4 Correct 1773 ms 99012 KB Output is correct
5 Correct 18 ms 23876 KB Output is correct
6 Correct 1240 ms 98792 KB Output is correct
7 Runtime error 145 ms 27768 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 25596 KB Output is correct
2 Correct 722 ms 106344 KB Output is correct
3 Correct 1126 ms 98624 KB Output is correct
4 Correct 1811 ms 99040 KB Output is correct
5 Correct 16 ms 23884 KB Output is correct
6 Correct 1367 ms 98612 KB Output is correct
7 Correct 62 ms 25540 KB Output is correct
8 Correct 724 ms 106344 KB Output is correct
9 Correct 1053 ms 98684 KB Output is correct
10 Correct 1773 ms 99012 KB Output is correct
11 Correct 18 ms 23876 KB Output is correct
12 Correct 1240 ms 98792 KB Output is correct
13 Runtime error 145 ms 27768 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 25596 KB Output is correct
2 Correct 722 ms 106344 KB Output is correct
3 Correct 1126 ms 98624 KB Output is correct
4 Correct 1811 ms 99040 KB Output is correct
5 Correct 16 ms 23884 KB Output is correct
6 Correct 1367 ms 98612 KB Output is correct
7 Correct 62 ms 25540 KB Output is correct
8 Correct 724 ms 106344 KB Output is correct
9 Correct 1053 ms 98684 KB Output is correct
10 Correct 1773 ms 99012 KB Output is correct
11 Correct 18 ms 23876 KB Output is correct
12 Correct 1240 ms 98792 KB Output is correct
13 Runtime error 145 ms 27768 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 25596 KB Output is correct
2 Correct 722 ms 106344 KB Output is correct
3 Correct 1126 ms 98624 KB Output is correct
4 Correct 1811 ms 99040 KB Output is correct
5 Correct 16 ms 23884 KB Output is correct
6 Correct 1367 ms 98612 KB Output is correct
7 Correct 62 ms 25540 KB Output is correct
8 Correct 724 ms 106344 KB Output is correct
9 Correct 1053 ms 98684 KB Output is correct
10 Correct 1773 ms 99012 KB Output is correct
11 Correct 18 ms 23876 KB Output is correct
12 Correct 1240 ms 98792 KB Output is correct
13 Runtime error 145 ms 27768 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -