oj.uz

Submission #406147

# Submission time Handle Problem Language Result Execution time Memory
406147 2021-05-17T08:49:10 Z errorgorn From Hacks to Snitches (BOI21_watchmen) C++17
25 / 100
 6000 ms 159916 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%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 32 ms 39928 KB Output is correct
2 Correct 111 ms 49200 KB Output is correct
3 Correct 101 ms 47716 KB Output is correct
4 Correct 115 ms 47304 KB Output is correct
5 Correct 23 ms 38612 KB Output is correct
6 Correct 93 ms 47668 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39876 KB Output is correct
2 Correct 109 ms 49216 KB Output is correct
3 Correct 106 ms 47716 KB Output is correct
4 Correct 119 ms 47348 KB Output is correct
5 Correct 22 ms 38544 KB Output is correct
6 Correct 85 ms 47532 KB Output is correct
7 Correct 107 ms 47792 KB Output is correct
8 Correct 79 ms 47856 KB Output is correct
9 Correct 101 ms 48060 KB Output is correct
10 Correct 103 ms 46836 KB Output is correct
11 Correct 138 ms 46304 KB Output is correct
12 Correct 150 ms 47444 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39876 KB Output is correct
2 Correct 109 ms 49216 KB Output is correct
3 Correct 106 ms 47716 KB Output is correct
4 Correct 119 ms 47348 KB Output is correct
5 Correct 22 ms 38544 KB Output is correct
6 Correct 85 ms 47532 KB Output is correct
7 Correct 107 ms 47792 KB Output is correct
8 Correct 79 ms 47856 KB Output is correct
9 Correct 101 ms 48060 KB Output is correct
10 Correct 103 ms 46836 KB Output is correct
11 Correct 138 ms 46304 KB Output is correct
12 Correct 150 ms 47444 KB Output is correct
13 Correct 31 ms 39844 KB Output is correct
14 Correct 132 ms 49192 KB Output is correct
15 Correct 100 ms 47732 KB Output is correct
16 Correct 143 ms 47384 KB Output is correct
17 Correct 26 ms 38468 KB Output is correct
18 Correct 103 ms 47556 KB Output is correct
19 Correct 134 ms 47772 KB Output is correct
20 Correct 105 ms 48048 KB Output is correct
21 Correct 91 ms 48016 KB Output is correct
22 Correct 98 ms 46840 KB Output is correct
23 Correct 143 ms 46276 KB Output is correct
24 Correct 144 ms 47424 KB Output is correct
25 Correct 1876 ms 94948 KB Output is correct
26 Correct 1678 ms 99824 KB Output is correct
27 Correct 1489 ms 95724 KB Output is correct
28 Correct 1052 ms 100304 KB Output is correct
29 Correct 1524 ms 88104 KB Output is correct
30 Correct 1612 ms 89228 KB Output is correct
31 Correct 1772 ms 95248 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39876 KB Output is correct
2 Correct 109 ms 49216 KB Output is correct
3 Correct 106 ms 47716 KB Output is correct
4 Correct 119 ms 47348 KB Output is correct
5 Correct 22 ms 38544 KB Output is correct
6 Correct 85 ms 47532 KB Output is correct
7 Correct 107 ms 47792 KB Output is correct
8 Correct 79 ms 47856 KB Output is correct
9 Correct 101 ms 48060 KB Output is correct
10 Correct 103 ms 46836 KB Output is correct
11 Correct 138 ms 46304 KB Output is correct
12 Correct 150 ms 47444 KB Output is correct
13 Correct 31 ms 39844 KB Output is correct
14 Correct 132 ms 49192 KB Output is correct
15 Correct 100 ms 47732 KB Output is correct
16 Correct 143 ms 47384 KB Output is correct
17 Correct 26 ms 38468 KB Output is correct
18 Correct 103 ms 47556 KB Output is correct
19 Correct 134 ms 47772 KB Output is correct
20 Correct 105 ms 48048 KB Output is correct
21 Correct 91 ms 48016 KB Output is correct
22 Correct 98 ms 46840 KB Output is correct
23 Correct 143 ms 46276 KB Output is correct
24 Correct 144 ms 47424 KB Output is correct
25 Correct 1876 ms 94948 KB Output is correct
26 Correct 1678 ms 99824 KB Output is correct
27 Correct 1489 ms 95724 KB Output is correct
28 Correct 1052 ms 100304 KB Output is correct
29 Correct 1524 ms 88104 KB Output is correct
30 Correct 1612 ms 89228 KB Output is correct
31 Correct 1772 ms 95248 KB Output is correct
32 Correct 29 ms 39916 KB Output is correct
33 Correct 110 ms 49184 KB Output is correct
34 Correct 98 ms 47688 KB Output is correct
35 Correct 146 ms 47304 KB Output is correct
36 Correct 27 ms 38604 KB Output is correct
37 Correct 145 ms 47492 KB Output is correct
38 Correct 107 ms 47800 KB Output is correct
39 Correct 88 ms 47836 KB Output is correct
40 Correct 104 ms 47976 KB Output is correct
41 Correct 105 ms 46864 KB Output is correct
42 Correct 104 ms 46244 KB Output is correct
43 Correct 96 ms 47364 KB Output is correct
44 Correct 1887 ms 92536 KB Output is correct
45 Correct 1707 ms 97468 KB Output is correct
46 Correct 1482 ms 93316 KB Output is correct
47 Correct 1168 ms 97908 KB Output is correct
48 Correct 1559 ms 85736 KB Output is correct
49 Correct 1636 ms 87464 KB Output is correct
50 Correct 1771 ms 95308 KB Output is correct
51 Correct 2059 ms 127624 KB Output is correct
52 Correct 2170 ms 159916 KB Output is correct
53 Correct 1839 ms 127720 KB Output is correct
54 Correct 1010 ms 92992 KB Output is correct
55 Execution timed out 6079 ms 103652 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 39928 KB Output is correct
2 Correct 111 ms 49200 KB Output is correct
3 Correct 101 ms 47716 KB Output is correct
4 Correct 115 ms 47304 KB Output is correct
5 Correct 23 ms 38612 KB Output is correct
6 Correct 93 ms 47668 KB Output is correct
7 Correct 29 ms 39876 KB Output is correct
8 Correct 109 ms 49216 KB Output is correct
9 Correct 106 ms 47716 KB Output is correct
10 Correct 119 ms 47348 KB Output is correct
11 Correct 22 ms 38544 KB Output is correct
12 Correct 85 ms 47532 KB Output is correct
13 Correct 107 ms 47792 KB Output is correct
14 Correct 79 ms 47856 KB Output is correct
15 Correct 101 ms 48060 KB Output is correct
16 Correct 103 ms 46836 KB Output is correct
17 Correct 138 ms 46304 KB Output is correct
18 Correct 150 ms 47444 KB Output is correct
19 Correct 26 ms 38436 KB Output is correct
20 Correct 28 ms 38368 KB Output is correct
21 Correct 28 ms 38408 KB Output is correct
22 Correct 38 ms 39860 KB Output is correct
23 Correct 134 ms 49184 KB Output is correct
24 Correct 103 ms 47712 KB Output is correct
25 Correct 129 ms 47388 KB Output is correct
26 Correct 28 ms 38536 KB Output is correct
27 Correct 109 ms 47560 KB Output is correct
28 Correct 100 ms 47804 KB Output is correct
29 Correct 109 ms 47920 KB Output is correct
30 Correct 98 ms 48032 KB Output is correct
31 Correct 106 ms 46828 KB Output is correct
32 Correct 93 ms 46384 KB Output is correct
33 Correct 117 ms 47372 KB Output is correct
34 Correct 1867 ms 92384 KB Output is correct
35 Correct 1838 ms 85092 KB Output is correct
36 Incorrect 1897 ms 87380 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 39928 KB Output is correct
2 Correct 111 ms 49200 KB Output is correct
3 Correct 101 ms 47716 KB Output is correct
4 Correct 115 ms 47304 KB Output is correct
5 Correct 23 ms 38612 KB Output is correct
6 Correct 93 ms 47668 KB Output is correct
7 Correct 29 ms 39876 KB Output is correct
8 Correct 109 ms 49216 KB Output is correct
9 Correct 106 ms 47716 KB Output is correct
10 Correct 119 ms 47348 KB Output is correct
11 Correct 22 ms 38544 KB Output is correct
12 Correct 85 ms 47532 KB Output is correct
13 Correct 107 ms 47792 KB Output is correct
14 Correct 79 ms 47856 KB Output is correct
15 Correct 101 ms 48060 KB Output is correct
16 Correct 103 ms 46836 KB Output is correct
17 Correct 138 ms 46304 KB Output is correct
18 Correct 150 ms 47444 KB Output is correct
19 Correct 31 ms 39844 KB Output is correct
20 Correct 132 ms 49192 KB Output is correct
21 Correct 100 ms 47732 KB Output is correct
22 Correct 143 ms 47384 KB Output is correct
23 Correct 26 ms 38468 KB Output is correct
24 Correct 103 ms 47556 KB Output is correct
25 Correct 134 ms 47772 KB Output is correct
26 Correct 105 ms 48048 KB Output is correct
27 Correct 91 ms 48016 KB Output is correct
28 Correct 98 ms 46840 KB Output is correct
29 Correct 143 ms 46276 KB Output is correct
30 Correct 144 ms 47424 KB Output is correct
31 Correct 1876 ms 94948 KB Output is correct
32 Correct 1678 ms 99824 KB Output is correct
33 Correct 1489 ms 95724 KB Output is correct
34 Correct 1052 ms 100304 KB Output is correct
35 Correct 1524 ms 88104 KB Output is correct
36 Correct 1612 ms 89228 KB Output is correct
37 Correct 1772 ms 95248 KB Output is correct
38 Correct 26 ms 38436 KB Output is correct
39 Correct 28 ms 38368 KB Output is correct
40 Correct 28 ms 38408 KB Output is correct
41 Correct 38 ms 39860 KB Output is correct
42 Correct 134 ms 49184 KB Output is correct
43 Correct 103 ms 47712 KB Output is correct
44 Correct 129 ms 47388 KB Output is correct
45 Correct 28 ms 38536 KB Output is correct
46 Correct 109 ms 47560 KB Output is correct
47 Correct 100 ms 47804 KB Output is correct
48 Correct 109 ms 47920 KB Output is correct
49 Correct 98 ms 48032 KB Output is correct
50 Correct 106 ms 46828 KB Output is correct
51 Correct 93 ms 46384 KB Output is correct
52 Correct 117 ms 47372 KB Output is correct
53 Correct 1867 ms 92384 KB Output is correct
54 Correct 1838 ms 85092 KB Output is correct
55 Incorrect 1897 ms 87380 KB Output isn't correct
56 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 39928 KB Output is correct
2 Correct 111 ms 49200 KB Output is correct
3 Correct 101 ms 47716 KB Output is correct
4 Correct 115 ms 47304 KB Output is correct
5 Correct 23 ms 38612 KB Output is correct
6 Correct 93 ms 47668 KB Output is correct
7 Correct 29 ms 39876 KB Output is correct
8 Correct 109 ms 49216 KB Output is correct
9 Correct 106 ms 47716 KB Output is correct
10 Correct 119 ms 47348 KB Output is correct
11 Correct 22 ms 38544 KB Output is correct
12 Correct 85 ms 47532 KB Output is correct
13 Correct 107 ms 47792 KB Output is correct
14 Correct 79 ms 47856 KB Output is correct
15 Correct 101 ms 48060 KB Output is correct
16 Correct 103 ms 46836 KB Output is correct
17 Correct 138 ms 46304 KB Output is correct
18 Correct 150 ms 47444 KB Output is correct
19 Correct 31 ms 39844 KB Output is correct
20 Correct 132 ms 49192 KB Output is correct
21 Correct 100 ms 47732 KB Output is correct
22 Correct 143 ms 47384 KB Output is correct
23 Correct 26 ms 38468 KB Output is correct
24 Correct 103 ms 47556 KB Output is correct
25 Correct 134 ms 47772 KB Output is correct
26 Correct 105 ms 48048 KB Output is correct
27 Correct 91 ms 48016 KB Output is correct
28 Correct 98 ms 46840 KB Output is correct
29 Correct 143 ms 46276 KB Output is correct
30 Correct 144 ms 47424 KB Output is correct
31 Correct 1876 ms 94948 KB Output is correct
32 Correct 1678 ms 99824 KB Output is correct
33 Correct 1489 ms 95724 KB Output is correct
34 Correct 1052 ms 100304 KB Output is correct
35 Correct 1524 ms 88104 KB Output is correct
36 Correct 1612 ms 89228 KB Output is correct
37 Correct 1772 ms 95248 KB Output is correct
38 Correct 29 ms 39916 KB Output is correct
39 Correct 110 ms 49184 KB Output is correct
40 Correct 98 ms 47688 KB Output is correct
41 Correct 146 ms 47304 KB Output is correct
42 Correct 27 ms 38604 KB Output is correct
43 Correct 145 ms 47492 KB Output is correct
44 Correct 107 ms 47800 KB Output is correct
45 Correct 88 ms 47836 KB Output is correct
46 Correct 104 ms 47976 KB Output is correct
47 Correct 105 ms 46864 KB Output is correct
48 Correct 104 ms 46244 KB Output is correct
49 Correct 96 ms 47364 KB Output is correct
50 Correct 1887 ms 92536 KB Output is correct
51 Correct 1707 ms 97468 KB Output is correct
52 Correct 1482 ms 93316 KB Output is correct
53 Correct 1168 ms 97908 KB Output is correct
54 Correct 1559 ms 85736 KB Output is correct
55 Correct 1636 ms 87464 KB Output is correct
56 Correct 1771 ms 95308 KB Output is correct
57 Correct 2059 ms 127624 KB Output is correct
58 Correct 2170 ms 159916 KB Output is correct
59 Correct 1839 ms 127720 KB Output is correct
60 Correct 1010 ms 92992 KB Output is correct
61 Execution timed out 6079 ms 103652 KB Time limit exceeded
62 Halted 0 ms 0 KB -