oj.uz

Submission #406163

# Submission time Handle Problem Language Result Execution time Memory
406163 2021-05-17T08:57:09 Z errorgorn From Hacks to Snitches (BOI21_watchmen) C++17
25 / 100
 6000 ms 159840 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=(weight+ped[n1])+fix(bad[it]-(weight+ped[n1]),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 30 ms 39364 KB Output is correct
2 Correct 96 ms 48064 KB Output is correct
3 Correct 90 ms 46556 KB Output is correct
4 Correct 113 ms 46248 KB Output is correct
5 Correct 26 ms 38604 KB Output is correct
6 Correct 90 ms 46336 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 39380 KB Output is correct
2 Correct 100 ms 48056 KB Output is correct
3 Correct 93 ms 46660 KB Output is correct
4 Correct 113 ms 46148 KB Output is correct
5 Correct 27 ms 38520 KB Output is correct
6 Correct 86 ms 46356 KB Output is correct
7 Correct 91 ms 46592 KB Output is correct
8 Correct 86 ms 46724 KB Output is correct
9 Correct 88 ms 46800 KB Output is correct
10 Correct 90 ms 45620 KB Output is correct
11 Correct 86 ms 45252 KB Output is correct
12 Correct 91 ms 46228 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 39380 KB Output is correct
2 Correct 100 ms 48056 KB Output is correct
3 Correct 93 ms 46660 KB Output is correct
4 Correct 113 ms 46148 KB Output is correct
5 Correct 27 ms 38520 KB Output is correct
6 Correct 86 ms 46356 KB Output is correct
7 Correct 91 ms 46592 KB Output is correct
8 Correct 86 ms 46724 KB Output is correct
9 Correct 88 ms 46800 KB Output is correct
10 Correct 90 ms 45620 KB Output is correct
11 Correct 86 ms 45252 KB Output is correct
12 Correct 91 ms 46228 KB Output is correct
13 Correct 31 ms 39376 KB Output is correct
14 Correct 101 ms 47964 KB Output is correct
15 Correct 89 ms 46520 KB Output is correct
16 Correct 112 ms 46184 KB Output is correct
17 Correct 25 ms 38548 KB Output is correct
18 Correct 87 ms 46340 KB Output is correct
19 Correct 92 ms 46676 KB Output is correct
20 Correct 92 ms 46788 KB Output is correct
21 Correct 90 ms 46800 KB Output is correct
22 Correct 93 ms 45732 KB Output is correct
23 Correct 82 ms 45092 KB Output is correct
24 Correct 91 ms 46272 KB Output is correct
25 Correct 1605 ms 93056 KB Output is correct
26 Correct 1478 ms 98344 KB Output is correct
27 Correct 1311 ms 94344 KB Output is correct
28 Correct 1006 ms 98852 KB Output is correct
29 Correct 1443 ms 86600 KB Output is correct
30 Correct 1502 ms 88628 KB Output is correct
31 Correct 1702 ms 95388 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 39380 KB Output is correct
2 Correct 100 ms 48056 KB Output is correct
3 Correct 93 ms 46660 KB Output is correct
4 Correct 113 ms 46148 KB Output is correct
5 Correct 27 ms 38520 KB Output is correct
6 Correct 86 ms 46356 KB Output is correct
7 Correct 91 ms 46592 KB Output is correct
8 Correct 86 ms 46724 KB Output is correct
9 Correct 88 ms 46800 KB Output is correct
10 Correct 90 ms 45620 KB Output is correct
11 Correct 86 ms 45252 KB Output is correct
12 Correct 91 ms 46228 KB Output is correct
13 Correct 31 ms 39376 KB Output is correct
14 Correct 101 ms 47964 KB Output is correct
15 Correct 89 ms 46520 KB Output is correct
16 Correct 112 ms 46184 KB Output is correct
17 Correct 25 ms 38548 KB Output is correct
18 Correct 87 ms 46340 KB Output is correct
19 Correct 92 ms 46676 KB Output is correct
20 Correct 92 ms 46788 KB Output is correct
21 Correct 90 ms 46800 KB Output is correct
22 Correct 93 ms 45732 KB Output is correct
23 Correct 82 ms 45092 KB Output is correct
24 Correct 91 ms 46272 KB Output is correct
25 Correct 1605 ms 93056 KB Output is correct
26 Correct 1478 ms 98344 KB Output is correct
27 Correct 1311 ms 94344 KB Output is correct
28 Correct 1006 ms 98852 KB Output is correct
29 Correct 1443 ms 86600 KB Output is correct
30 Correct 1502 ms 88628 KB Output is correct
31 Correct 1702 ms 95388 KB Output is correct
32 Correct 31 ms 39436 KB Output is correct
33 Correct 99 ms 48128 KB Output is correct
34 Correct 91 ms 46856 KB Output is correct
35 Correct 115 ms 46344 KB Output is correct
36 Correct 25 ms 38476 KB Output is correct
37 Correct 88 ms 46532 KB Output is correct
38 Correct 94 ms 46788 KB Output is correct
39 Correct 96 ms 46940 KB Output is correct
40 Correct 91 ms 46920 KB Output is correct
41 Correct 91 ms 45784 KB Output is correct
42 Correct 83 ms 45252 KB Output is correct
43 Correct 88 ms 46492 KB Output is correct
44 Correct 1616 ms 92708 KB Output is correct
45 Correct 1450 ms 97632 KB Output is correct
46 Correct 1294 ms 93408 KB Output is correct
47 Correct 1020 ms 97924 KB Output is correct
48 Correct 1414 ms 86016 KB Output is correct
49 Correct 1498 ms 87292 KB Output is correct
50 Correct 1694 ms 95204 KB Output is correct
51 Correct 1978 ms 127608 KB Output is correct
52 Correct 2094 ms 159840 KB Output is correct
53 Correct 1719 ms 127736 KB Output is correct
54 Correct 990 ms 93028 KB Output is correct
55 Execution timed out 6047 ms 100276 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 39364 KB Output is correct
2 Correct 96 ms 48064 KB Output is correct
3 Correct 90 ms 46556 KB Output is correct
4 Correct 113 ms 46248 KB Output is correct
5 Correct 26 ms 38604 KB Output is correct
6 Correct 90 ms 46336 KB Output is correct
7 Correct 33 ms 39380 KB Output is correct
8 Correct 100 ms 48056 KB Output is correct
9 Correct 93 ms 46660 KB Output is correct
10 Correct 113 ms 46148 KB Output is correct
11 Correct 27 ms 38520 KB Output is correct
12 Correct 86 ms 46356 KB Output is correct
13 Correct 91 ms 46592 KB Output is correct
14 Correct 86 ms 46724 KB Output is correct
15 Correct 88 ms 46800 KB Output is correct
16 Correct 90 ms 45620 KB Output is correct
17 Correct 86 ms 45252 KB Output is correct
18 Correct 91 ms 46228 KB Output is correct
19 Correct 24 ms 38428 KB Output is correct
20 Correct 24 ms 38444 KB Output is correct
21 Correct 27 ms 38476 KB Output is correct
22 Correct 31 ms 39380 KB Output is correct
23 Correct 103 ms 48068 KB Output is correct
24 Correct 88 ms 46620 KB Output is correct
25 Correct 115 ms 46240 KB Output is correct
26 Correct 25 ms 38544 KB Output is correct
27 Correct 89 ms 46388 KB Output is correct
28 Correct 90 ms 46628 KB Output is correct
29 Correct 92 ms 46752 KB Output is correct
30 Correct 87 ms 46916 KB Output is correct
31 Correct 90 ms 45812 KB Output is correct
32 Correct 84 ms 45164 KB Output is correct
33 Correct 90 ms 46280 KB Output is correct
34 Correct 1725 ms 91336 KB Output is correct
35 Correct 1725 ms 85028 KB Output is correct
36 Incorrect 1741 ms 87312 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 39364 KB Output is correct
2 Correct 96 ms 48064 KB Output is correct
3 Correct 90 ms 46556 KB Output is correct
4 Correct 113 ms 46248 KB Output is correct
5 Correct 26 ms 38604 KB Output is correct
6 Correct 90 ms 46336 KB Output is correct
7 Correct 33 ms 39380 KB Output is correct
8 Correct 100 ms 48056 KB Output is correct
9 Correct 93 ms 46660 KB Output is correct
10 Correct 113 ms 46148 KB Output is correct
11 Correct 27 ms 38520 KB Output is correct
12 Correct 86 ms 46356 KB Output is correct
13 Correct 91 ms 46592 KB Output is correct
14 Correct 86 ms 46724 KB Output is correct
15 Correct 88 ms 46800 KB Output is correct
16 Correct 90 ms 45620 KB Output is correct
17 Correct 86 ms 45252 KB Output is correct
18 Correct 91 ms 46228 KB Output is correct
19 Correct 31 ms 39376 KB Output is correct
20 Correct 101 ms 47964 KB Output is correct
21 Correct 89 ms 46520 KB Output is correct
22 Correct 112 ms 46184 KB Output is correct
23 Correct 25 ms 38548 KB Output is correct
24 Correct 87 ms 46340 KB Output is correct
25 Correct 92 ms 46676 KB Output is correct
26 Correct 92 ms 46788 KB Output is correct
27 Correct 90 ms 46800 KB Output is correct
28 Correct 93 ms 45732 KB Output is correct
29 Correct 82 ms 45092 KB Output is correct
30 Correct 91 ms 46272 KB Output is correct
31 Correct 1605 ms 93056 KB Output is correct
32 Correct 1478 ms 98344 KB Output is correct
33 Correct 1311 ms 94344 KB Output is correct
34 Correct 1006 ms 98852 KB Output is correct
35 Correct 1443 ms 86600 KB Output is correct
36 Correct 1502 ms 88628 KB Output is correct
37 Correct 1702 ms 95388 KB Output is correct
38 Correct 24 ms 38428 KB Output is correct
39 Correct 24 ms 38444 KB Output is correct
40 Correct 27 ms 38476 KB Output is correct
41 Correct 31 ms 39380 KB Output is correct
42 Correct 103 ms 48068 KB Output is correct
43 Correct 88 ms 46620 KB Output is correct
44 Correct 115 ms 46240 KB Output is correct
45 Correct 25 ms 38544 KB Output is correct
46 Correct 89 ms 46388 KB Output is correct
47 Correct 90 ms 46628 KB Output is correct
48 Correct 92 ms 46752 KB Output is correct
49 Correct 87 ms 46916 KB Output is correct
50 Correct 90 ms 45812 KB Output is correct
51 Correct 84 ms 45164 KB Output is correct
52 Correct 90 ms 46280 KB Output is correct
53 Correct 1725 ms 91336 KB Output is correct
54 Correct 1725 ms 85028 KB Output is correct
55 Incorrect 1741 ms 87312 KB Output isn't correct
56 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 39364 KB Output is correct
2 Correct 96 ms 48064 KB Output is correct
3 Correct 90 ms 46556 KB Output is correct
4 Correct 113 ms 46248 KB Output is correct
5 Correct 26 ms 38604 KB Output is correct
6 Correct 90 ms 46336 KB Output is correct
7 Correct 33 ms 39380 KB Output is correct
8 Correct 100 ms 48056 KB Output is correct
9 Correct 93 ms 46660 KB Output is correct
10 Correct 113 ms 46148 KB Output is correct
11 Correct 27 ms 38520 KB Output is correct
12 Correct 86 ms 46356 KB Output is correct
13 Correct 91 ms 46592 KB Output is correct
14 Correct 86 ms 46724 KB Output is correct
15 Correct 88 ms 46800 KB Output is correct
16 Correct 90 ms 45620 KB Output is correct
17 Correct 86 ms 45252 KB Output is correct
18 Correct 91 ms 46228 KB Output is correct
19 Correct 31 ms 39376 KB Output is correct
20 Correct 101 ms 47964 KB Output is correct
21 Correct 89 ms 46520 KB Output is correct
22 Correct 112 ms 46184 KB Output is correct
23 Correct 25 ms 38548 KB Output is correct
24 Correct 87 ms 46340 KB Output is correct
25 Correct 92 ms 46676 KB Output is correct
26 Correct 92 ms 46788 KB Output is correct
27 Correct 90 ms 46800 KB Output is correct
28 Correct 93 ms 45732 KB Output is correct
29 Correct 82 ms 45092 KB Output is correct
30 Correct 91 ms 46272 KB Output is correct
31 Correct 1605 ms 93056 KB Output is correct
32 Correct 1478 ms 98344 KB Output is correct
33 Correct 1311 ms 94344 KB Output is correct
34 Correct 1006 ms 98852 KB Output is correct
35 Correct 1443 ms 86600 KB Output is correct
36 Correct 1502 ms 88628 KB Output is correct
37 Correct 1702 ms 95388 KB Output is correct
38 Correct 31 ms 39436 KB Output is correct
39 Correct 99 ms 48128 KB Output is correct
40 Correct 91 ms 46856 KB Output is correct
41 Correct 115 ms 46344 KB Output is correct
42 Correct 25 ms 38476 KB Output is correct
43 Correct 88 ms 46532 KB Output is correct
44 Correct 94 ms 46788 KB Output is correct
45 Correct 96 ms 46940 KB Output is correct
46 Correct 91 ms 46920 KB Output is correct
47 Correct 91 ms 45784 KB Output is correct
48 Correct 83 ms 45252 KB Output is correct
49 Correct 88 ms 46492 KB Output is correct
50 Correct 1616 ms 92708 KB Output is correct
51 Correct 1450 ms 97632 KB Output is correct
52 Correct 1294 ms 93408 KB Output is correct
53 Correct 1020 ms 97924 KB Output is correct
54 Correct 1414 ms 86016 KB Output is correct
55 Correct 1498 ms 87292 KB Output is correct
56 Correct 1694 ms 95204 KB Output is correct
57 Correct 1978 ms 127608 KB Output is correct
58 Correct 2094 ms 159840 KB Output is correct
59 Correct 1719 ms 127736 KB Output is correct
60 Correct 990 ms 93028 KB Output is correct
61 Execution timed out 6047 ms 100276 KB Time limit exceeded
62 Halted 0 ms 0 KB -