oj.uz

Submission #703632

# Submission time Handle Problem Language Result Execution time Memory
703632 2023-02-27T21:56:25 Z kinope From Hacks to Snitches (BOI21_watchmen) C++14
15 / 100
 6000 ms 291572 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef pair<int, int> pii;
struct info{
		int x, k, mod;
		info(){}
		info(int x, int k, int mod) : x(x), k(k), mod(mod) {}
};void get(int &a){
		char c = getchar_unlocked(); a = 0;
		while(c<'0'||'9'<c) c = getchar_unlocked();
		while('0'<=c&&c<='9') a = (a<<3)+(a<<1)+c-'0', c = getchar_unlocked();
}
int main(){
		int n, m, a, b; get(n), get(m);
		vector<vector<int>> g(n+1);
		for(int i = 0; i < m; ++i) get(a), get(b), g[a].emplace_back(b), g[b].emplace_back(a);
		int k; get(k);
		vector<pii> ktcykl(n+1);
		vector<int> sz(k+1); sz[0] = 1;
		vector<vector<vector<int>>> dp(n+1);
		for(int i = 1; i <= n; ++i) dp[i].resize(k+1);
		for(int i = 1; i <= n; ++i) dp[i][0].emplace_back(2e09);
		for(int i = 1; i <= k; ++i){
				get(b), sz[i] = b;
				for(int j = 1; j <= n; ++j) dp[j][i].resize(b, 2e09);
				for(int j = 0; j < b; ++j) get(a), ktcykl[a] = pii(i, j);
		}
		queue<info> q;
		for(int i = 0; i <= k; ++i) q.emplace(1, i, 0), dp[1][i][0] = 0;
		while(!q.empty()){
				info x = q.front(); q.pop();
				int odl = dp[x.x][x.k][x.mod];
				//printf("%d %d %d: %d\n", x.x, x.k, x.mod, dp[x.x][x.k][x.mod]);
				if(!ktcykl[x.x].ff){
						for(int u : g[x.x]){
								//printf("%d %d\n", x.x, u);
								if(!ktcykl[u].ff) for(int i = 0; i <= k; ++i){ if(dp[u][i][(odl+1)%sz[i]] > odl+1) q.emplace(u, i, (odl+1)%sz[i]), dp[u][i][(odl+1)%sz[i]] = odl+1;}
								else if(ktcykl[u].ss != (odl+1)%sz[ktcykl[u].ff]) for(int i = 0; i <= k; ++i) if(dp[u][i][(odl+1)%sz[i]] > odl+1) q.emplace(u, i, (odl+1)%sz[i]), dp[u][i][(odl+1)%sz[i]] = odl+1;
						}
						if(dp[x.x][x.k][(x.mod+1)%sz[x.k]] > odl+1) q.emplace(x.x, x.k, (x.mod+1)%sz[x.k]), dp[x.x][x.k][(x.mod+1)%sz[x.k]] = odl+1;
				}
				else{
						for(int u : g[x.x]){
								if(ktcykl[x.x].ff != ktcykl[u].ff){
										if(!ktcykl[u].ff) for(int i = 0; i <= k; ++i){ if(dp[u][i][(odl+1)%sz[i]] > odl+1) q.emplace(u, i, (odl+1)%sz[i]), dp[u][i][(odl+1)%sz[i]] = odl+1;}
										else if(ktcykl[u].ss != (odl+1)%sz[ktcykl[u].ff]) for(int i = 0; i <= k; ++i) if(dp[u][i][(odl+1)%sz[i]] > odl+1) q.emplace(u, i, (odl+1)%sz[i]), dp[u][i][(odl+1)%sz[i]] = odl+1;
								}
								else{
										if(ktcykl[u].ss == (odl+1)%sz[ktcykl[u].ff] || (ktcykl[x.x].ss == (odl+1)%sz[ktcykl[u].ff] && ktcykl[u].ss == odl%sz[ktcykl[u].ff])){/*printf("!!%d %d %d: %d   %d %d\n", x.x, x.k, x.mod, u, ktcykl[x.x].ss, ktcykl[u].ss); */continue;}
										else for(int i = 0; i <= k; ++i) if(dp[u][i][(odl+1)%sz[i]] > odl+1) q.emplace(u, i, (odl+1)%sz[i]), dp[u][i][(odl+1)%sz[i]] = odl+1;
								}
						}
						if(ktcykl[x.x].ss != (odl+1)%sz[ktcykl[x.x].ff] && dp[x.x][x.k][(x.mod+1)%sz[x.k]] > odl+1) q.emplace(x.x, x.k, (x.mod+1)%sz[x.k]), dp[x.x][x.k][(x.mod+1)%sz[x.k]] = odl+1;
				}
		}
		int wynik = 2e09;
		for(int i = 0; i <= k; ++i)
				for(int j = 0; j < sz[i]; ++j) wynik = min(wynik, dp[n][i][j]);
		
		if(wynik == 2e09) printf("impossible\n");
		else printf("%d\n", wynik);
		
		return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 1984 KB Output is correct
2 Correct 954 ms 69056 KB Output is correct
3 Correct 1776 ms 62500 KB Output is correct
4 Correct 2746 ms 63104 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2044 ms 62756 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 1876 KB Output is correct
2 Correct 943 ms 69036 KB Output is correct
3 Correct 1717 ms 62640 KB Output is correct
4 Correct 2632 ms 63096 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2049 ms 62700 KB Output is correct
7 Correct 1311 ms 64176 KB Output is correct
8 Correct 1356 ms 68504 KB Output is correct
9 Correct 2109 ms 87028 KB Output is correct
10 Correct 1940 ms 64660 KB Output is correct
11 Correct 2308 ms 87816 KB Output is correct
12 Correct 1917 ms 65972 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 1876 KB Output is correct
2 Correct 943 ms 69036 KB Output is correct
3 Correct 1717 ms 62640 KB Output is correct
4 Correct 2632 ms 63096 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2049 ms 62700 KB Output is correct
7 Correct 1311 ms 64176 KB Output is correct
8 Correct 1356 ms 68504 KB Output is correct
9 Correct 2109 ms 87028 KB Output is correct
10 Correct 1940 ms 64660 KB Output is correct
11 Correct 2308 ms 87816 KB Output is correct
12 Correct 1917 ms 65972 KB Output is correct
13 Correct 244 ms 1976 KB Output is correct
14 Correct 951 ms 69032 KB Output is correct
15 Correct 1752 ms 62624 KB Output is correct
16 Correct 2731 ms 63080 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1974 ms 62704 KB Output is correct
19 Correct 1292 ms 64304 KB Output is correct
20 Correct 1357 ms 68560 KB Output is correct
21 Correct 2078 ms 87048 KB Output is correct
22 Correct 1854 ms 64656 KB Output is correct
23 Correct 2261 ms 87788 KB Output is correct
24 Correct 1815 ms 65952 KB Output is correct
25 Execution timed out 6026 ms 278492 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 1876 KB Output is correct
2 Correct 943 ms 69036 KB Output is correct
3 Correct 1717 ms 62640 KB Output is correct
4 Correct 2632 ms 63096 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2049 ms 62700 KB Output is correct
7 Correct 1311 ms 64176 KB Output is correct
8 Correct 1356 ms 68504 KB Output is correct
9 Correct 2109 ms 87028 KB Output is correct
10 Correct 1940 ms 64660 KB Output is correct
11 Correct 2308 ms 87816 KB Output is correct
12 Correct 1917 ms 65972 KB Output is correct
13 Correct 244 ms 1976 KB Output is correct
14 Correct 951 ms 69032 KB Output is correct
15 Correct 1752 ms 62624 KB Output is correct
16 Correct 2731 ms 63080 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1974 ms 62704 KB Output is correct
19 Correct 1292 ms 64304 KB Output is correct
20 Correct 1357 ms 68560 KB Output is correct
21 Correct 2078 ms 87048 KB Output is correct
22 Correct 1854 ms 64656 KB Output is correct
23 Correct 2261 ms 87788 KB Output is correct
24 Correct 1815 ms 65952 KB Output is correct
25 Execution timed out 6026 ms 278492 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 1984 KB Output is correct
2 Correct 954 ms 69056 KB Output is correct
3 Correct 1776 ms 62500 KB Output is correct
4 Correct 2746 ms 63104 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2044 ms 62756 KB Output is correct
7 Correct 257 ms 1876 KB Output is correct
8 Correct 943 ms 69036 KB Output is correct
9 Correct 1717 ms 62640 KB Output is correct
10 Correct 2632 ms 63096 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2049 ms 62700 KB Output is correct
13 Correct 1311 ms 64176 KB Output is correct
14 Correct 1356 ms 68504 KB Output is correct
15 Correct 2109 ms 87028 KB Output is correct
16 Correct 1940 ms 64660 KB Output is correct
17 Correct 2308 ms 87816 KB Output is correct
18 Correct 1917 ms 65972 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 300 KB Output is correct
22 Correct 238 ms 1780 KB Output is correct
23 Correct 916 ms 68840 KB Output is correct
24 Correct 1810 ms 62244 KB Output is correct
25 Correct 2648 ms 62840 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 2068 ms 62500 KB Output is correct
28 Correct 1357 ms 63920 KB Output is correct
29 Correct 1335 ms 68176 KB Output is correct
30 Correct 2064 ms 86892 KB Output is correct
31 Correct 1839 ms 64400 KB Output is correct
32 Correct 2265 ms 87536 KB Output is correct
33 Correct 1838 ms 65776 KB Output is correct
34 Execution timed out 6059 ms 291572 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 1984 KB Output is correct
2 Correct 954 ms 69056 KB Output is correct
3 Correct 1776 ms 62500 KB Output is correct
4 Correct 2746 ms 63104 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2044 ms 62756 KB Output is correct
7 Correct 257 ms 1876 KB Output is correct
8 Correct 943 ms 69036 KB Output is correct
9 Correct 1717 ms 62640 KB Output is correct
10 Correct 2632 ms 63096 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2049 ms 62700 KB Output is correct
13 Correct 1311 ms 64176 KB Output is correct
14 Correct 1356 ms 68504 KB Output is correct
15 Correct 2109 ms 87028 KB Output is correct
16 Correct 1940 ms 64660 KB Output is correct
17 Correct 2308 ms 87816 KB Output is correct
18 Correct 1917 ms 65972 KB Output is correct
19 Correct 244 ms 1976 KB Output is correct
20 Correct 951 ms 69032 KB Output is correct
21 Correct 1752 ms 62624 KB Output is correct
22 Correct 2731 ms 63080 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1974 ms 62704 KB Output is correct
25 Correct 1292 ms 64304 KB Output is correct
26 Correct 1357 ms 68560 KB Output is correct
27 Correct 2078 ms 87048 KB Output is correct
28 Correct 1854 ms 64656 KB Output is correct
29 Correct 2261 ms 87788 KB Output is correct
30 Correct 1815 ms 65952 KB Output is correct
31 Execution timed out 6026 ms 278492 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 1984 KB Output is correct
2 Correct 954 ms 69056 KB Output is correct
3 Correct 1776 ms 62500 KB Output is correct
4 Correct 2746 ms 63104 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2044 ms 62756 KB Output is correct
7 Correct 257 ms 1876 KB Output is correct
8 Correct 943 ms 69036 KB Output is correct
9 Correct 1717 ms 62640 KB Output is correct
10 Correct 2632 ms 63096 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2049 ms 62700 KB Output is correct
13 Correct 1311 ms 64176 KB Output is correct
14 Correct 1356 ms 68504 KB Output is correct
15 Correct 2109 ms 87028 KB Output is correct
16 Correct 1940 ms 64660 KB Output is correct
17 Correct 2308 ms 87816 KB Output is correct
18 Correct 1917 ms 65972 KB Output is correct
19 Correct 244 ms 1976 KB Output is correct
20 Correct 951 ms 69032 KB Output is correct
21 Correct 1752 ms 62624 KB Output is correct
22 Correct 2731 ms 63080 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1974 ms 62704 KB Output is correct
25 Correct 1292 ms 64304 KB Output is correct
26 Correct 1357 ms 68560 KB Output is correct
27 Correct 2078 ms 87048 KB Output is correct
28 Correct 1854 ms 64656 KB Output is correct
29 Correct 2261 ms 87788 KB Output is correct
30 Correct 1815 ms 65952 KB Output is correct
31 Execution timed out 6026 ms 278492 KB Time limit exceeded
32 Halted 0 ms 0 KB -