답안 #657515

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
657515	2022-11-10T02:12:13 Z	Lobo	From Hacks to Snitches (BOI21_watchmen)	C++17	35 / 100	3092 ms	109116 KB

watchmen

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()

const int inf = 1e9+10;
const int maxn = 3e5+10;

int n, m, k;
int szrt[maxn], idrt[maxn], thrt[maxn], isrt[maxn], nxrt[maxn], pvrt[maxn], dlol[maxn];
vector<int> g[maxn], d[maxn];

int32_t main() {
    // freopen("in.in", "r", stdin);

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u,v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    cin >> k;
    for(int i = 1; i <= k; i++) {
        cin >> szrt[i];
        for(int j = 0; j < szrt[i]; j++) {
            int v; cin >> v;
            idrt[v] = i;
            isrt[v] = 1;
            thrt[v] = j;
        }
    }

    szrt[0] = 1;
    for(int i = 1; i <= n; i++) {
        dlol[i] = inf;
        if(isrt[i]) {
            for(int j = 0; j < szrt[idrt[i]]; j++) {
                d[i].pb(inf);
            }
            int u = i;
            for(auto v : g[u]) {
                if(isrt[v] && idrt[u] == idrt[v] && thrt[v] == (thrt[u]+1)%szrt[idrt[u]]) {
                    nxrt[u] = v;
                }
                if(isrt[v] && idrt[u] == idrt[v] && thrt[u] == (thrt[v]+1)%szrt[idrt[u]]) {
                    pvrt[u] = v;
                }
            }
        }
        else {
            d[i].pb(inf);
        }

    }

    d[1][0] = 0;
    priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> pq;
    pq.push(mp(0,mp(1,0)));
    while(pq.size()) {
        int u = pq.top().sc.fr;
        int t = pq.top().sc.sc;
        int dist = pq.top().fr;
        pq.pop();

        if(t != -1 && dist != d[u][t]) continue;
        if(t == -1 && dist != dlol[u]) continue;

        if(t == -1) {
            for(auto v : g[u]) {
                if(isrt[v]) {
                    int d1 = dlol[u]+1;
                    int t1 = d1%szrt[idrt[v]];
                    // Vou encontrar o guarda em v ou indo para v
                    // indo para v == u é depois de v e em t1 ele vai estar em u
                    if(t1 == thrt[v] || (thrt[u] == (thrt[v]+1)%szrt[idrt[u]] && t1 == thrt[u])) continue;
                    if(d[v][t1] > d1) {
                        d[v][t1] = d1;
                        pq.push(mp(d[v][t1],mp(v,t1)));
                    }
                }
                else {
                    int d1 = dlol[u]+1;
                    int t1 = 0;
                    if(d[v][t1] > d1) {
                        d[v][t1] = d1;
                        pq.push(mp(d[v][t1],mp(v,t1)));
                    }
                }
            }
            continue;
        }

        if(isrt[u]) {
            for(auto v : g[u]) {
                // if(v == nxrt[u] || v == pvrt[u]) {
                // // if(isrt[v]) {
                //     int d1 = d[u][t]+1;
                //     int t1 = d1%szrt[idrt[v]];
                //     // Vou encontrar o guarda em v ou indo para v
                //     // indo para v == u é depois de v e em t1 ele vai estar em u
                //     if(t1 == thrt[v] || (thrt[u] == (thrt[v]+1)%szrt[idrt[u]] && t1 == thrt[u])) continue;
                //     if(d[v][t1] > d1) {
                //         d[v][t1] = d1;
                //         pq.push(mp(d[v][t1],mp(v,t1)));
                //     }
                // }
                
            }

            int v,d1,t1;
            v = nxrt[u];
            d1 = d[u][t]+1;
            t1 = d1%szrt[idrt[v]];
            // Vou encontrar o guarda em v ou indo para v
            // indo para v == u é depois de v e em t1 ele vai estar em u
            if(!(t1 == thrt[v] || (thrt[u] == (thrt[v]+1)%szrt[idrt[u]] && t1 == thrt[u])) && d[v][t1] > d1) {
                d[v][t1] = d1;
                pq.push(mp(d[v][t1],mp(v,t1)));
            }

            v = pvrt[u];
            d1 = d[u][t]+1;
            t1 = d1%szrt[idrt[v]];
            // Vou encontrar o guarda em v ou indo para v
            // indo para v == u é depois de v e em t1 ele vai estar em u
            if(!(t1 == thrt[v] || (thrt[u] == (thrt[v]+1)%szrt[idrt[u]] && t1 == thrt[u])) && d[v][t1] > d1) {
                d[v][t1] = d1;
                pq.push(mp(d[v][t1],mp(v,t1)));
            }

            if(dlol[u] > d[u][t]) {
                dlol[u] = d[u][t];
                pq.push(mp(dlol[u],mp(u,-1)));
            }
        }
        else {
            for(auto v : g[u]) {
                if(isrt[v]) {
                    // d[u][t]+1+i = (thrt[v]+1) MOD
                    // i = trrt[v]-d[u][t] MOD
                    int i = ((thrt[v]-d[u][t])%szrt[idrt[v]]+szrt[idrt[v]])%szrt[idrt[v]];
                    int d1 = d[u][t]+1+i;
                    int t1 = d1%szrt[idrt[v]];
                    if(t1 == thrt[v]) continue;
                    if(d[v][t1] > d1) {
                        d[v][t1] = d1;
                        pq.push(mp(d[v][t1],mp(v,t1)));
                    }
                    d1 = d[u][t]+1;
                    t1 = d1%szrt[idrt[v]];
                    if(t1 == thrt[v]) continue;
                    if(d[v][t1] > d1) {
                        d[v][t1] = d1;
                        pq.push(mp(d[v][t1],mp(v,t1)));
                    }
                }
                else {
                    int d1 = d[u][t]+1;
                    int t1 = 0;
                    if(d[v][t1] > d1) {
                        d[v][t1] = d1;
                        pq.push(mp(d[v][t1],mp(v,t1)));
                    }
                }
            }
        }
    }

    if(d[n][0] == inf) cout << "impossible" << endl;
    else cout << d[n][0] << endl;
}

Compilation message

watchmen.cpp: In function 'int32_t main()':
watchmen.cpp:99:22: warning: unused variable 'v' [-Wunused-variable]
   99 |             for(auto v : g[u]) {
      |                      ^

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	15320 KB	Output is correct
2	Correct	103 ms	22468 KB	Output is correct
3	Correct	107 ms	21932 KB	Output is correct
4	Correct	110 ms	21972 KB	Output is correct
5	Correct	8 ms	14420 KB	Output is correct
6	Correct	108 ms	21964 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	15312 KB	Output is correct
2	Correct	109 ms	22568 KB	Output is correct
3	Correct	106 ms	21960 KB	Output is correct
4	Correct	103 ms	21932 KB	Output is correct
5	Correct	8 ms	14420 KB	Output is correct
6	Correct	108 ms	21992 KB	Output is correct
7	Correct	104 ms	21912 KB	Output is correct
8	Correct	97 ms	21836 KB	Output is correct
9	Correct	104 ms	21820 KB	Output is correct
10	Correct	100 ms	22048 KB	Output is correct
11	Correct	109 ms	21984 KB	Output is correct
12	Correct	99 ms	21932 KB	Output is correct

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	15312 KB	Output is correct
2	Correct	109 ms	22568 KB	Output is correct
3	Correct	106 ms	21960 KB	Output is correct
4	Correct	103 ms	21932 KB	Output is correct
5	Correct	8 ms	14420 KB	Output is correct
6	Correct	108 ms	21992 KB	Output is correct
7	Correct	104 ms	21912 KB	Output is correct
8	Correct	97 ms	21836 KB	Output is correct
9	Correct	104 ms	21820 KB	Output is correct
10	Correct	100 ms	22048 KB	Output is correct
11	Correct	109 ms	21984 KB	Output is correct
12	Correct	99 ms	21932 KB	Output is correct
13	Correct	41 ms	15324 KB	Output is correct
14	Correct	112 ms	22524 KB	Output is correct
15	Correct	101 ms	21928 KB	Output is correct
16	Correct	111 ms	22136 KB	Output is correct
17	Correct	8 ms	14420 KB	Output is correct
18	Correct	107 ms	21860 KB	Output is correct
19	Correct	106 ms	21908 KB	Output is correct
20	Correct	101 ms	21892 KB	Output is correct
21	Correct	97 ms	21848 KB	Output is correct
22	Correct	114 ms	22104 KB	Output is correct
23	Correct	100 ms	21960 KB	Output is correct
24	Correct	103 ms	21880 KB	Output is correct
25	Correct	2487 ms	66108 KB	Output is correct
26	Correct	2371 ms	71336 KB	Output is correct
27	Correct	2292 ms	67064 KB	Output is correct
28	Correct	2035 ms	70932 KB	Output is correct
29	Correct	2375 ms	61468 KB	Output is correct
30	Correct	2359 ms	64760 KB	Output is correct
31	Correct	2621 ms	71424 KB	Output is correct

Subtask #4

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	15312 KB	Output is correct
2	Correct	109 ms	22568 KB	Output is correct
3	Correct	106 ms	21960 KB	Output is correct
4	Correct	103 ms	21932 KB	Output is correct
5	Correct	8 ms	14420 KB	Output is correct
6	Correct	108 ms	21992 KB	Output is correct
7	Correct	104 ms	21912 KB	Output is correct
8	Correct	97 ms	21836 KB	Output is correct
9	Correct	104 ms	21820 KB	Output is correct
10	Correct	100 ms	22048 KB	Output is correct
11	Correct	109 ms	21984 KB	Output is correct
12	Correct	99 ms	21932 KB	Output is correct
13	Correct	41 ms	15324 KB	Output is correct
14	Correct	112 ms	22524 KB	Output is correct
15	Correct	101 ms	21928 KB	Output is correct
16	Correct	111 ms	22136 KB	Output is correct
17	Correct	8 ms	14420 KB	Output is correct
18	Correct	107 ms	21860 KB	Output is correct
19	Correct	106 ms	21908 KB	Output is correct
20	Correct	101 ms	21892 KB	Output is correct
21	Correct	97 ms	21848 KB	Output is correct
22	Correct	114 ms	22104 KB	Output is correct
23	Correct	100 ms	21960 KB	Output is correct
24	Correct	103 ms	21880 KB	Output is correct
25	Correct	2487 ms	66108 KB	Output is correct
26	Correct	2371 ms	71336 KB	Output is correct
27	Correct	2292 ms	67064 KB	Output is correct
28	Correct	2035 ms	70932 KB	Output is correct
29	Correct	2375 ms	61468 KB	Output is correct
30	Correct	2359 ms	64760 KB	Output is correct
31	Correct	2621 ms	71424 KB	Output is correct
32	Correct	41 ms	15344 KB	Output is correct
33	Correct	108 ms	22504 KB	Output is correct
34	Correct	171 ms	21932 KB	Output is correct
35	Correct	106 ms	22040 KB	Output is correct
36	Correct	8 ms	14416 KB	Output is correct
37	Correct	104 ms	21804 KB	Output is correct
38	Correct	168 ms	21916 KB	Output is correct
39	Correct	125 ms	21892 KB	Output is correct
40	Correct	118 ms	21876 KB	Output is correct
41	Correct	117 ms	22080 KB	Output is correct
42	Correct	97 ms	21964 KB	Output is correct
43	Correct	106 ms	21932 KB	Output is correct
44	Correct	2697 ms	66016 KB	Output is correct
45	Correct	2633 ms	71144 KB	Output is correct
46	Correct	2387 ms	66944 KB	Output is correct
47	Correct	2158 ms	70864 KB	Output is correct
48	Correct	2430 ms	61444 KB	Output is correct
49	Correct	2415 ms	64860 KB	Output is correct
50	Correct	2810 ms	71248 KB	Output is correct
51	Correct	2975 ms	79928 KB	Output is correct
52	Correct	3092 ms	94484 KB	Output is correct
53	Correct	2717 ms	78300 KB	Output is correct
54	Correct	2092 ms	63884 KB	Output is correct
55	Correct	2933 ms	80704 KB	Output is correct
56	Correct	2857 ms	109116 KB	Output is correct

Subtask #5

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	15320 KB	Output is correct
2	Correct	103 ms	22468 KB	Output is correct
3	Correct	107 ms	21932 KB	Output is correct
4	Correct	110 ms	21972 KB	Output is correct
5	Correct	8 ms	14420 KB	Output is correct
6	Correct	108 ms	21964 KB	Output is correct
7	Correct	41 ms	15312 KB	Output is correct
8	Correct	109 ms	22568 KB	Output is correct
9	Correct	106 ms	21960 KB	Output is correct
10	Correct	103 ms	21932 KB	Output is correct
11	Correct	8 ms	14420 KB	Output is correct
12	Correct	108 ms	21992 KB	Output is correct
13	Correct	104 ms	21912 KB	Output is correct
14	Correct	97 ms	21836 KB	Output is correct
15	Correct	104 ms	21820 KB	Output is correct
16	Correct	100 ms	22048 KB	Output is correct
17	Correct	109 ms	21984 KB	Output is correct
18	Correct	99 ms	21932 KB	Output is correct
19	Correct	7 ms	14420 KB	Output is correct
20	Correct	7 ms	14368 KB	Output is correct
21	Correct	7 ms	14420 KB	Output is correct
22	Correct	40 ms	15308 KB	Output is correct
23	Correct	140 ms	22452 KB	Output is correct
24	Correct	114 ms	22036 KB	Output is correct
25	Correct	115 ms	21936 KB	Output is correct
26	Correct	9 ms	14420 KB	Output is correct
27	Correct	107 ms	21836 KB	Output is correct
28	Correct	108 ms	21860 KB	Output is correct
29	Correct	112 ms	21884 KB	Output is correct
30	Correct	108 ms	21816 KB	Output is correct
31	Correct	109 ms	22048 KB	Output is correct
32	Correct	106 ms	21980 KB	Output is correct
33	Correct	112 ms	21836 KB	Output is correct
34	Correct	2910 ms	66096 KB	Output is correct
35	Correct	2862 ms	62468 KB	Output is correct
36	Correct	2779 ms	62568 KB	Output is correct
37	Incorrect	2378 ms	67572 KB	Output isn't correct
38	Halted	0 ms	0 KB	-

Subtask #6

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	15320 KB	Output is correct
2	Correct	103 ms	22468 KB	Output is correct
3	Correct	107 ms	21932 KB	Output is correct
4	Correct	110 ms	21972 KB	Output is correct
5	Correct	8 ms	14420 KB	Output is correct
6	Correct	108 ms	21964 KB	Output is correct
7	Correct	41 ms	15312 KB	Output is correct
8	Correct	109 ms	22568 KB	Output is correct
9	Correct	106 ms	21960 KB	Output is correct
10	Correct	103 ms	21932 KB	Output is correct
11	Correct	8 ms	14420 KB	Output is correct
12	Correct	108 ms	21992 KB	Output is correct
13	Correct	104 ms	21912 KB	Output is correct
14	Correct	97 ms	21836 KB	Output is correct
15	Correct	104 ms	21820 KB	Output is correct
16	Correct	100 ms	22048 KB	Output is correct
17	Correct	109 ms	21984 KB	Output is correct
18	Correct	99 ms	21932 KB	Output is correct
19	Correct	41 ms	15324 KB	Output is correct
20	Correct	112 ms	22524 KB	Output is correct
21	Correct	101 ms	21928 KB	Output is correct
22	Correct	111 ms	22136 KB	Output is correct
23	Correct	8 ms	14420 KB	Output is correct
24	Correct	107 ms	21860 KB	Output is correct
25	Correct	106 ms	21908 KB	Output is correct
26	Correct	101 ms	21892 KB	Output is correct
27	Correct	97 ms	21848 KB	Output is correct
28	Correct	114 ms	22104 KB	Output is correct
29	Correct	100 ms	21960 KB	Output is correct
30	Correct	103 ms	21880 KB	Output is correct
31	Correct	2487 ms	66108 KB	Output is correct
32	Correct	2371 ms	71336 KB	Output is correct
33	Correct	2292 ms	67064 KB	Output is correct
34	Correct	2035 ms	70932 KB	Output is correct
35	Correct	2375 ms	61468 KB	Output is correct
36	Correct	2359 ms	64760 KB	Output is correct
37	Correct	2621 ms	71424 KB	Output is correct
38	Correct	7 ms	14420 KB	Output is correct
39	Correct	7 ms	14368 KB	Output is correct
40	Correct	7 ms	14420 KB	Output is correct
41	Correct	40 ms	15308 KB	Output is correct
42	Correct	140 ms	22452 KB	Output is correct
43	Correct	114 ms	22036 KB	Output is correct
44	Correct	115 ms	21936 KB	Output is correct
45	Correct	9 ms	14420 KB	Output is correct
46	Correct	107 ms	21836 KB	Output is correct
47	Correct	108 ms	21860 KB	Output is correct
48	Correct	112 ms	21884 KB	Output is correct
49	Correct	108 ms	21816 KB	Output is correct
50	Correct	109 ms	22048 KB	Output is correct
51	Correct	106 ms	21980 KB	Output is correct
52	Correct	112 ms	21836 KB	Output is correct
53	Correct	2910 ms	66096 KB	Output is correct
54	Correct	2862 ms	62468 KB	Output is correct
55	Correct	2779 ms	62568 KB	Output is correct
56	Incorrect	2378 ms	67572 KB	Output isn't correct
57	Halted	0 ms	0 KB	-

Subtask #7

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	15320 KB	Output is correct
2	Correct	103 ms	22468 KB	Output is correct
3	Correct	107 ms	21932 KB	Output is correct
4	Correct	110 ms	21972 KB	Output is correct
5	Correct	8 ms	14420 KB	Output is correct
6	Correct	108 ms	21964 KB	Output is correct
7	Correct	41 ms	15312 KB	Output is correct
8	Correct	109 ms	22568 KB	Output is correct
9	Correct	106 ms	21960 KB	Output is correct
10	Correct	103 ms	21932 KB	Output is correct
11	Correct	8 ms	14420 KB	Output is correct
12	Correct	108 ms	21992 KB	Output is correct
13	Correct	104 ms	21912 KB	Output is correct
14	Correct	97 ms	21836 KB	Output is correct
15	Correct	104 ms	21820 KB	Output is correct
16	Correct	100 ms	22048 KB	Output is correct
17	Correct	109 ms	21984 KB	Output is correct
18	Correct	99 ms	21932 KB	Output is correct
19	Correct	41 ms	15324 KB	Output is correct
20	Correct	112 ms	22524 KB	Output is correct
21	Correct	101 ms	21928 KB	Output is correct
22	Correct	111 ms	22136 KB	Output is correct
23	Correct	8 ms	14420 KB	Output is correct
24	Correct	107 ms	21860 KB	Output is correct
25	Correct	106 ms	21908 KB	Output is correct
26	Correct	101 ms	21892 KB	Output is correct
27	Correct	97 ms	21848 KB	Output is correct
28	Correct	114 ms	22104 KB	Output is correct
29	Correct	100 ms	21960 KB	Output is correct
30	Correct	103 ms	21880 KB	Output is correct
31	Correct	2487 ms	66108 KB	Output is correct
32	Correct	2371 ms	71336 KB	Output is correct
33	Correct	2292 ms	67064 KB	Output is correct
34	Correct	2035 ms	70932 KB	Output is correct
35	Correct	2375 ms	61468 KB	Output is correct
36	Correct	2359 ms	64760 KB	Output is correct
37	Correct	2621 ms	71424 KB	Output is correct
38	Correct	41 ms	15344 KB	Output is correct
39	Correct	108 ms	22504 KB	Output is correct
40	Correct	171 ms	21932 KB	Output is correct
41	Correct	106 ms	22040 KB	Output is correct
42	Correct	8 ms	14416 KB	Output is correct
43	Correct	104 ms	21804 KB	Output is correct
44	Correct	168 ms	21916 KB	Output is correct
45	Correct	125 ms	21892 KB	Output is correct
46	Correct	118 ms	21876 KB	Output is correct
47	Correct	117 ms	22080 KB	Output is correct
48	Correct	97 ms	21964 KB	Output is correct
49	Correct	106 ms	21932 KB	Output is correct
50	Correct	2697 ms	66016 KB	Output is correct
51	Correct	2633 ms	71144 KB	Output is correct
52	Correct	2387 ms	66944 KB	Output is correct
53	Correct	2158 ms	70864 KB	Output is correct
54	Correct	2430 ms	61444 KB	Output is correct
55	Correct	2415 ms	64860 KB	Output is correct
56	Correct	2810 ms	71248 KB	Output is correct
57	Correct	2975 ms	79928 KB	Output is correct
58	Correct	3092 ms	94484 KB	Output is correct
59	Correct	2717 ms	78300 KB	Output is correct
60	Correct	2092 ms	63884 KB	Output is correct
61	Correct	2933 ms	80704 KB	Output is correct
62	Correct	2857 ms	109116 KB	Output is correct
63	Correct	7 ms	14420 KB	Output is correct
64	Correct	7 ms	14368 KB	Output is correct
65	Correct	7 ms	14420 KB	Output is correct
66	Correct	40 ms	15308 KB	Output is correct
67	Correct	140 ms	22452 KB	Output is correct
68	Correct	114 ms	22036 KB	Output is correct
69	Correct	115 ms	21936 KB	Output is correct
70	Correct	9 ms	14420 KB	Output is correct
71	Correct	107 ms	21836 KB	Output is correct
72	Correct	108 ms	21860 KB	Output is correct
73	Correct	112 ms	21884 KB	Output is correct
74	Correct	108 ms	21816 KB	Output is correct
75	Correct	109 ms	22048 KB	Output is correct
76	Correct	106 ms	21980 KB	Output is correct
77	Correct	112 ms	21836 KB	Output is correct
78	Correct	2910 ms	66096 KB	Output is correct
79	Correct	2862 ms	62468 KB	Output is correct
80	Correct	2779 ms	62568 KB	Output is correct
81	Incorrect	2378 ms	67572 KB	Output isn't correct
82	Halted	0 ms	0 KB	-