oj.uz

Submission #406154

# Submission time Handle Problem Language Result Execution time Memory
406154 2021-05-17T08:52:54 Z errorgorn From Hacks to Snitches (BOI21_watchmen) C++17
25 / 100
 6000 ms 159864 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e)?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

int n,m,k;
vector<ii> edges;

vector<int> w[250005]; //period is implicit here
vector<int> al[250005];

int id[250005]; //which watchmen
int bad[250005]; //when the watchmen comes
int ped[250005];

vector<ii> dial[1000005];

void read(int &x){
	x=0;
	char ch=getchar_unlocked();
	while (ch&16){
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
}

int fix(int i,int j){
	i%=j;
	if (i<0) i+=j;
	return i;
}

void upd(int k,int i,int j){
	if (w[i][j]>k){
		w[i][j]=k;
		//pq.push(iii(k,ii(i,j)));
		if (k>1000000) return;
		dial[k].pub(ii(i,j));
	}
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	read(n),read(m);
	
	int a,b;
	rep(x,0,m){
		read(a),read(b);
		al[a].pub(b);
		al[b].pub(a);
	}
	
	memset(ped,-1,sizeof(ped));
	memset(id,-1,sizeof(id));
	memset(bad,-1,sizeof(bad));
	
	read(k);
	rep(x,0,k){
		read(a);
		
		vector<int> path;
		rep(y,0,a){
			read(b);
			
			path.pub(b);
			bad[b]=y;
			id[b]=x;
			ped[b]=a;
		}
	}
	
	rep(x,1,n+1){
		if (ped[x]==-1) w[x].pub(1e9);
		else{
			rep(y,0,ped[x]) w[x].pub(1e9);
		}
	}
	
	upd(0,1,0);
	
	int weight=0;
	while (weight<1000000){
		if (dial[weight].empty()){
			weight++;
			continue;
		}
		
		int n1,n2;
		tie(n1,n2)=dial[weight].back();
		dial[weight].pob();
		
		if (w[n1][n2]!=weight) continue;
		if (ped[n1]!=-1 && weight%ped[n1]==bad[n1]) continue;
		//same position as watchmen
		
		if (n1==n){
			cout<<weight<<endl;
			return 0;
		}
		
		//cout<<weight<<" "<<n1<<" "<<n2<<" "<<ped[n1]<<" "<<bad[n1]<<endl;
		
		for (int x=0;x<sz(al[n1]);x++){
			auto it=al[n1][x];
			
			if (ped[it]==-1){
				//normal dijkstra into node without period
				int ww=weight;
				if (n1<=n) ww++;
				upd(ww,it,0);
				
				//delete the edge
				swap(al[n1][x],al[n1].back());
				al[n1].pob();
				x--;
			}
			else if (ped[n1]==-1 && ped[it]!=-1){
				//node without period into node with period
				int ww=weight+1;
				upd(ww,it,ww%ped[it]);
				
				//also need one that lands immediately after watchmen pass
				ww=weight+fix(bad[it]-weight,ped[it])+1;
				upd(ww,it,ww%ped[it]);
			}
			else if (id[n1]==id[it]){
				//same watchmen
				int ww=weight+1;
				
				if ((bad[it]+1)%ped[it]==bad[n1] && ww%ped[it]==bad[n1]) continue;
				upd(ww,it,ww%ped[it]);
			}
			else{
				//different watchmen
				
				//time that watchmen on other side steps on it
				int tt=weight+fix(bad[it]-weight,ped[it]);
				
				if (tt%ped[n1]==bad[n1]){ //cannot come back to our side
					upd(weight+1,it,weight%ped[it]);
					upd(weight+1+ped[n1],it,(weight+1+ped[n1])%ped[it]);
					
					tt+=ped[it];
					if (tt%ped[n1]!=bad[n1]) upd(tt+1,it,(tt+1)%ped[it]);
				}
				else{ //ok we can update all it
					upd(weight+1,it,weight%ped[it]);
					upd(tt+1,it,(tt+1)%ped[it]);
					
					//delete the edge
					swap(al[n1][x],al[n1].back());
					al[n1].pob();
					x--;
				}
			}
		}
		
		if (ped[n1]!=-1){
			upd(weight+1,n1,(n2+1)%ped[n1]);
		}
	}
	
	
	/*
	rep(x,1,IDX){
		cout<<x<<": ";
		for (auto &it:w[x]) cout<<it<<" "; cout<<endl;
	}
	//*/
	
	cout<<"impossible"<<endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39396 KB Output is correct
2 Correct 89 ms 47996 KB Output is correct
3 Correct 83 ms 46532 KB Output is correct
4 Correct 125 ms 46144 KB Output is correct
5 Correct 22 ms 38604 KB Output is correct
6 Correct 83 ms 46420 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39392 KB Output is correct
2 Correct 89 ms 48068 KB Output is correct
3 Correct 84 ms 46600 KB Output is correct
4 Correct 117 ms 46160 KB Output is correct
5 Correct 22 ms 38604 KB Output is correct
6 Correct 88 ms 46408 KB Output is correct
7 Correct 82 ms 46624 KB Output is correct
8 Correct 88 ms 46728 KB Output is correct
9 Correct 81 ms 46788 KB Output is correct
10 Correct 87 ms 45656 KB Output is correct
11 Correct 78 ms 45064 KB Output is correct
12 Correct 78 ms 46292 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39392 KB Output is correct
2 Correct 89 ms 48068 KB Output is correct
3 Correct 84 ms 46600 KB Output is correct
4 Correct 117 ms 46160 KB Output is correct
5 Correct 22 ms 38604 KB Output is correct
6 Correct 88 ms 46408 KB Output is correct
7 Correct 82 ms 46624 KB Output is correct
8 Correct 88 ms 46728 KB Output is correct
9 Correct 81 ms 46788 KB Output is correct
10 Correct 87 ms 45656 KB Output is correct
11 Correct 78 ms 45064 KB Output is correct
12 Correct 78 ms 46292 KB Output is correct
13 Correct 27 ms 39372 KB Output is correct
14 Correct 97 ms 48048 KB Output is correct
15 Correct 88 ms 46736 KB Output is correct
16 Correct 111 ms 46204 KB Output is correct
17 Correct 22 ms 38524 KB Output is correct
18 Correct 80 ms 46404 KB Output is correct
19 Correct 89 ms 46604 KB Output is correct
20 Correct 83 ms 46720 KB Output is correct
21 Correct 89 ms 46916 KB Output is correct
22 Correct 87 ms 45612 KB Output is correct
23 Correct 74 ms 45108 KB Output is correct
24 Correct 79 ms 46288 KB Output is correct
25 Correct 1605 ms 92292 KB Output is correct
26 Correct 1410 ms 98608 KB Output is correct
27 Correct 1305 ms 94608 KB Output is correct
28 Correct 906 ms 99200 KB Output is correct
29 Correct 1462 ms 87068 KB Output is correct
30 Correct 1488 ms 89044 KB Output is correct
31 Correct 1656 ms 95348 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39392 KB Output is correct
2 Correct 89 ms 48068 KB Output is correct
3 Correct 84 ms 46600 KB Output is correct
4 Correct 117 ms 46160 KB Output is correct
5 Correct 22 ms 38604 KB Output is correct
6 Correct 88 ms 46408 KB Output is correct
7 Correct 82 ms 46624 KB Output is correct
8 Correct 88 ms 46728 KB Output is correct
9 Correct 81 ms 46788 KB Output is correct
10 Correct 87 ms 45656 KB Output is correct
11 Correct 78 ms 45064 KB Output is correct
12 Correct 78 ms 46292 KB Output is correct
13 Correct 27 ms 39372 KB Output is correct
14 Correct 97 ms 48048 KB Output is correct
15 Correct 88 ms 46736 KB Output is correct
16 Correct 111 ms 46204 KB Output is correct
17 Correct 22 ms 38524 KB Output is correct
18 Correct 80 ms 46404 KB Output is correct
19 Correct 89 ms 46604 KB Output is correct
20 Correct 83 ms 46720 KB Output is correct
21 Correct 89 ms 46916 KB Output is correct
22 Correct 87 ms 45612 KB Output is correct
23 Correct 74 ms 45108 KB Output is correct
24 Correct 79 ms 46288 KB Output is correct
25 Correct 1605 ms 92292 KB Output is correct
26 Correct 1410 ms 98608 KB Output is correct
27 Correct 1305 ms 94608 KB Output is correct
28 Correct 906 ms 99200 KB Output is correct
29 Correct 1462 ms 87068 KB Output is correct
30 Correct 1488 ms 89044 KB Output is correct
31 Correct 1656 ms 95348 KB Output is correct
32 Correct 31 ms 39820 KB Output is correct
33 Correct 110 ms 48516 KB Output is correct
34 Correct 85 ms 47036 KB Output is correct
35 Correct 110 ms 46504 KB Output is correct
36 Correct 22 ms 38496 KB Output is correct
37 Correct 85 ms 46692 KB Output is correct
38 Correct 82 ms 46728 KB Output is correct
39 Correct 88 ms 46912 KB Output is correct
40 Correct 82 ms 46816 KB Output is correct
41 Correct 94 ms 45684 KB Output is correct
42 Correct 85 ms 45176 KB Output is correct
43 Correct 82 ms 46244 KB Output is correct
44 Correct 1532 ms 92336 KB Output is correct
45 Correct 1409 ms 97416 KB Output is correct
46 Correct 1198 ms 93232 KB Output is correct
47 Correct 952 ms 97944 KB Output is correct
48 Correct 1402 ms 85696 KB Output is correct
49 Correct 1504 ms 87268 KB Output is correct
50 Correct 1722 ms 95200 KB Output is correct
51 Correct 1856 ms 127412 KB Output is correct
52 Correct 1875 ms 159864 KB Output is correct
53 Correct 1568 ms 127660 KB Output is correct
54 Correct 900 ms 92808 KB Output is correct
55 Execution timed out 6063 ms 99460 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39396 KB Output is correct
2 Correct 89 ms 47996 KB Output is correct
3 Correct 83 ms 46532 KB Output is correct
4 Correct 125 ms 46144 KB Output is correct
5 Correct 22 ms 38604 KB Output is correct
6 Correct 83 ms 46420 KB Output is correct
7 Correct 28 ms 39392 KB Output is correct
8 Correct 89 ms 48068 KB Output is correct
9 Correct 84 ms 46600 KB Output is correct
10 Correct 117 ms 46160 KB Output is correct
11 Correct 22 ms 38604 KB Output is correct
12 Correct 88 ms 46408 KB Output is correct
13 Correct 82 ms 46624 KB Output is correct
14 Correct 88 ms 46728 KB Output is correct
15 Correct 81 ms 46788 KB Output is correct
16 Correct 87 ms 45656 KB Output is correct
17 Correct 78 ms 45064 KB Output is correct
18 Correct 78 ms 46292 KB Output is correct
19 Correct 22 ms 38420 KB Output is correct
20 Correct 22 ms 38476 KB Output is correct
21 Correct 24 ms 38468 KB Output is correct
22 Correct 29 ms 39372 KB Output is correct
23 Correct 92 ms 48064 KB Output is correct
24 Correct 88 ms 46572 KB Output is correct
25 Correct 105 ms 46180 KB Output is correct
26 Correct 24 ms 38484 KB Output is correct
27 Correct 81 ms 46360 KB Output is correct
28 Correct 81 ms 46788 KB Output is correct
29 Correct 82 ms 46660 KB Output is correct
30 Correct 95 ms 46876 KB Output is correct
31 Correct 93 ms 45616 KB Output is correct
32 Correct 84 ms 45112 KB Output is correct
33 Correct 82 ms 46212 KB Output is correct
34 Correct 1548 ms 90340 KB Output is correct
35 Correct 1706 ms 85048 KB Output is correct
36 Incorrect 1753 ms 87256 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39396 KB Output is correct
2 Correct 89 ms 47996 KB Output is correct
3 Correct 83 ms 46532 KB Output is correct
4 Correct 125 ms 46144 KB Output is correct
5 Correct 22 ms 38604 KB Output is correct
6 Correct 83 ms 46420 KB Output is correct
7 Correct 28 ms 39392 KB Output is correct
8 Correct 89 ms 48068 KB Output is correct
9 Correct 84 ms 46600 KB Output is correct
10 Correct 117 ms 46160 KB Output is correct
11 Correct 22 ms 38604 KB Output is correct
12 Correct 88 ms 46408 KB Output is correct
13 Correct 82 ms 46624 KB Output is correct
14 Correct 88 ms 46728 KB Output is correct
15 Correct 81 ms 46788 KB Output is correct
16 Correct 87 ms 45656 KB Output is correct
17 Correct 78 ms 45064 KB Output is correct
18 Correct 78 ms 46292 KB Output is correct
19 Correct 27 ms 39372 KB Output is correct
20 Correct 97 ms 48048 KB Output is correct
21 Correct 88 ms 46736 KB Output is correct
22 Correct 111 ms 46204 KB Output is correct
23 Correct 22 ms 38524 KB Output is correct
24 Correct 80 ms 46404 KB Output is correct
25 Correct 89 ms 46604 KB Output is correct
26 Correct 83 ms 46720 KB Output is correct
27 Correct 89 ms 46916 KB Output is correct
28 Correct 87 ms 45612 KB Output is correct
29 Correct 74 ms 45108 KB Output is correct
30 Correct 79 ms 46288 KB Output is correct
31 Correct 1605 ms 92292 KB Output is correct
32 Correct 1410 ms 98608 KB Output is correct
33 Correct 1305 ms 94608 KB Output is correct
34 Correct 906 ms 99200 KB Output is correct
35 Correct 1462 ms 87068 KB Output is correct
36 Correct 1488 ms 89044 KB Output is correct
37 Correct 1656 ms 95348 KB Output is correct
38 Correct 22 ms 38420 KB Output is correct
39 Correct 22 ms 38476 KB Output is correct
40 Correct 24 ms 38468 KB Output is correct
41 Correct 29 ms 39372 KB Output is correct
42 Correct 92 ms 48064 KB Output is correct
43 Correct 88 ms 46572 KB Output is correct
44 Correct 105 ms 46180 KB Output is correct
45 Correct 24 ms 38484 KB Output is correct
46 Correct 81 ms 46360 KB Output is correct
47 Correct 81 ms 46788 KB Output is correct
48 Correct 82 ms 46660 KB Output is correct
49 Correct 95 ms 46876 KB Output is correct
50 Correct 93 ms 45616 KB Output is correct
51 Correct 84 ms 45112 KB Output is correct
52 Correct 82 ms 46212 KB Output is correct
53 Correct 1548 ms 90340 KB Output is correct
54 Correct 1706 ms 85048 KB Output is correct
55 Incorrect 1753 ms 87256 KB Output isn't correct
56 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39396 KB Output is correct
2 Correct 89 ms 47996 KB Output is correct
3 Correct 83 ms 46532 KB Output is correct
4 Correct 125 ms 46144 KB Output is correct
5 Correct 22 ms 38604 KB Output is correct
6 Correct 83 ms 46420 KB Output is correct
7 Correct 28 ms 39392 KB Output is correct
8 Correct 89 ms 48068 KB Output is correct
9 Correct 84 ms 46600 KB Output is correct
10 Correct 117 ms 46160 KB Output is correct
11 Correct 22 ms 38604 KB Output is correct
12 Correct 88 ms 46408 KB Output is correct
13 Correct 82 ms 46624 KB Output is correct
14 Correct 88 ms 46728 KB Output is correct
15 Correct 81 ms 46788 KB Output is correct
16 Correct 87 ms 45656 KB Output is correct
17 Correct 78 ms 45064 KB Output is correct
18 Correct 78 ms 46292 KB Output is correct
19 Correct 27 ms 39372 KB Output is correct
20 Correct 97 ms 48048 KB Output is correct
21 Correct 88 ms 46736 KB Output is correct
22 Correct 111 ms 46204 KB Output is correct
23 Correct 22 ms 38524 KB Output is correct
24 Correct 80 ms 46404 KB Output is correct
25 Correct 89 ms 46604 KB Output is correct
26 Correct 83 ms 46720 KB Output is correct
27 Correct 89 ms 46916 KB Output is correct
28 Correct 87 ms 45612 KB Output is correct
29 Correct 74 ms 45108 KB Output is correct
30 Correct 79 ms 46288 KB Output is correct
31 Correct 1605 ms 92292 KB Output is correct
32 Correct 1410 ms 98608 KB Output is correct
33 Correct 1305 ms 94608 KB Output is correct
34 Correct 906 ms 99200 KB Output is correct
35 Correct 1462 ms 87068 KB Output is correct
36 Correct 1488 ms 89044 KB Output is correct
37 Correct 1656 ms 95348 KB Output is correct
38 Correct 31 ms 39820 KB Output is correct
39 Correct 110 ms 48516 KB Output is correct
40 Correct 85 ms 47036 KB Output is correct
41 Correct 110 ms 46504 KB Output is correct
42 Correct 22 ms 38496 KB Output is correct
43 Correct 85 ms 46692 KB Output is correct
44 Correct 82 ms 46728 KB Output is correct
45 Correct 88 ms 46912 KB Output is correct
46 Correct 82 ms 46816 KB Output is correct
47 Correct 94 ms 45684 KB Output is correct
48 Correct 85 ms 45176 KB Output is correct
49 Correct 82 ms 46244 KB Output is correct
50 Correct 1532 ms 92336 KB Output is correct
51 Correct 1409 ms 97416 KB Output is correct
52 Correct 1198 ms 93232 KB Output is correct
53 Correct 952 ms 97944 KB Output is correct
54 Correct 1402 ms 85696 KB Output is correct
55 Correct 1504 ms 87268 KB Output is correct
56 Correct 1722 ms 95200 KB Output is correct
57 Correct 1856 ms 127412 KB Output is correct
58 Correct 1875 ms 159864 KB Output is correct
59 Correct 1568 ms 127660 KB Output is correct
60 Correct 900 ms 92808 KB Output is correct
61 Execution timed out 6063 ms 99460 KB Time limit exceeded
62 Halted 0 ms 0 KB -