oj.uz

답안 #426384

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
426384 2021-06-13T22:06:57 Z duality From Hacks to Snitches (BOI21_watchmen) C++11
50 / 100
 6000 ms 147324 KB 
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

vi adjList[250000];
pair<int,pii> p[250000];
bool comp(int a,int b) {
    return p[a] < p[b];
}
int pos[250000];
vector<LLI> dist[250000];
priority_queue<pair<LLI,int> > H;
int relax(int u,LLI d) {
    if ((dist[u][d % p[u].first] == -1) || (d < dist[u][d % p[u].first])) {
        dist[u][d % p[u].first] = d;
        H.push(mp(-d,u));
    }
    return 0;
}
int done[250000],done2[250000];
int main() {
    int i,j;
    int N,M,K;
    int u,v,l;
    scanf("%d %d",&N,&M);
    for (i = 0; i < M; i++) {
        scanf("%d %d",&u,&v);
        u--,v--;
        adjList[u].pb(v);
        adjList[v].pb(u);
    }
    scanf("%d",&K);
    for (i = 0; i < K; i++) {
        scanf("%d",&l);
        for (j = 0; j < l; j++) scanf("%d",&v),p[v-1] = mp(l,mp(j,i));
    }

    for (i = 0; i < N; i++) {
        if (p[i].first == 0) p[i].first = 1;
        dist[i].resize(p[i].first);
        fill(dist[i].begin(),dist[i].end(),-1);
    }
    for (i = 0; i < N; i++) {
        sort(adjList[i].begin(),adjList[i].end(),comp);
        while ((pos[i] < adjList[i].size()) && (p[adjList[i][pos[i]]].first == 1)) pos[i]++;
    }
    dist[0][0] = 0,H.push(mp(0,0));
    while (!H.empty()) {
        int u = H.top().second;
        LLI d = -H.top().first;
        H.pop();

        if (d > dist[u][d % p[u].first]) continue;
        else if (u == N-1) {
            printf("%lld\n",d);
            return 0;
        }
        if ((p[u].first == 1) || (((d+1) % p[u].first) != p[u].second.first)) relax(u,d+1);
        for (i = done[u] ? pos[u]:0; i < adjList[u].size(); i++) {
            int v = adjList[u][i];
            if (p[v].first == 1) relax(v,d+1);
            else if (p[u].first == 1) {
                if (done2[v]) continue;
                else {
                    for (j = 0; j < p[v].first; j++) {
                        LLI d2 = d+j+1;
                        if ((d2 % p[v].first) != p[v].second.first) relax(v,d2);
                    }
                    done2[v] = 1;
                }
            }
            else if (p[u].second.second == p[v].second.second) {
                if (((d+1) % p[v].first) == p[v].second.first) continue;
                if (((d % p[v].first) == p[v].second.first) && (((d+1) % p[u].first) == p[u].second.first)) continue;
                relax(v,d+1);
            }
            else {
                for (j = 0; j < p[v].first; j++) {
                    LLI d2 = d+(LLI) j*p[u].first+1;
                    if ((d2 % p[v].first) != p[v].second.first) relax(v,d2);
                }
            }
        }
        done[u] = 1;
    }
    printf("impossible\n");

    return 0;
}

Compilation message

watchmen.cpp: In function 'int main()':
watchmen.cpp:50:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         while ((pos[i] < adjList[i].size()) && (p[adjList[i][pos[i]]].first == 1)) pos[i]++;
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:64:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (i = done[u] ? pos[u]:0; i < adjList[u].size(); i++) {
      |                                      ~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
watchmen.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~
watchmen.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d",&K);
      |     ~~~~~^~~~~~~~~
watchmen.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf("%d",&l);
      |         ~~~~~^~~~~~~~~
watchmen.cpp:40:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         for (j = 0; j < l; j++) scanf("%d",&v),p[v-1] = mp(l,mp(j,i));
      |                                 ~~~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 13492 KB Output is correct
2 Correct 120 ms 20820 KB Output is correct
3 Correct 153 ms 20416 KB Output is correct
4 Correct 185 ms 20680 KB Output is correct
5 Correct 9 ms 12192 KB Output is correct
6 Correct 102 ms 20316 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 13484 KB Output is correct
2 Correct 106 ms 20508 KB Output is correct
3 Correct 106 ms 20388 KB Output is correct
4 Correct 140 ms 20684 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 111 ms 20420 KB Output is correct
7 Correct 126 ms 19860 KB Output is correct
8 Correct 105 ms 20084 KB Output is correct
9 Correct 97 ms 19780 KB Output is correct
10 Correct 119 ms 20348 KB Output is correct
11 Correct 106 ms 20140 KB Output is correct
12 Correct 130 ms 20092 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 13484 KB Output is correct
2 Correct 106 ms 20508 KB Output is correct
3 Correct 106 ms 20388 KB Output is correct
4 Correct 140 ms 20684 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 111 ms 20420 KB Output is correct
7 Correct 126 ms 19860 KB Output is correct
8 Correct 105 ms 20084 KB Output is correct
9 Correct 97 ms 19780 KB Output is correct
10 Correct 119 ms 20348 KB Output is correct
11 Correct 106 ms 20140 KB Output is correct
12 Correct 130 ms 20092 KB Output is correct
13 Correct 36 ms 13380 KB Output is correct
14 Correct 115 ms 20620 KB Output is correct
15 Correct 119 ms 20392 KB Output is correct
16 Correct 151 ms 20676 KB Output is correct
17 Correct 9 ms 12108 KB Output is correct
18 Correct 116 ms 20520 KB Output is correct
19 Correct 102 ms 19948 KB Output is correct
20 Correct 104 ms 20140 KB Output is correct
21 Correct 118 ms 19892 KB Output is correct
22 Correct 146 ms 20296 KB Output is correct
23 Correct 116 ms 20184 KB Output is correct
24 Correct 108 ms 20164 KB Output is correct
25 Correct 2611 ms 65504 KB Output is correct
26 Correct 2783 ms 69912 KB Output is correct
27 Correct 2418 ms 66472 KB Output is correct
28 Correct 2021 ms 69296 KB Output is correct
29 Correct 2747 ms 63008 KB Output is correct
30 Correct 2891 ms 65452 KB Output is correct
31 Correct 3147 ms 70440 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 13484 KB Output is correct
2 Correct 106 ms 20508 KB Output is correct
3 Correct 106 ms 20388 KB Output is correct
4 Correct 140 ms 20684 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 111 ms 20420 KB Output is correct
7 Correct 126 ms 19860 KB Output is correct
8 Correct 105 ms 20084 KB Output is correct
9 Correct 97 ms 19780 KB Output is correct
10 Correct 119 ms 20348 KB Output is correct
11 Correct 106 ms 20140 KB Output is correct
12 Correct 130 ms 20092 KB Output is correct
13 Correct 36 ms 13380 KB Output is correct
14 Correct 115 ms 20620 KB Output is correct
15 Correct 119 ms 20392 KB Output is correct
16 Correct 151 ms 20676 KB Output is correct
17 Correct 9 ms 12108 KB Output is correct
18 Correct 116 ms 20520 KB Output is correct
19 Correct 102 ms 19948 KB Output is correct
20 Correct 104 ms 20140 KB Output is correct
21 Correct 118 ms 19892 KB Output is correct
22 Correct 146 ms 20296 KB Output is correct
23 Correct 116 ms 20184 KB Output is correct
24 Correct 108 ms 20164 KB Output is correct
25 Correct 2611 ms 65504 KB Output is correct
26 Correct 2783 ms 69912 KB Output is correct
27 Correct 2418 ms 66472 KB Output is correct
28 Correct 2021 ms 69296 KB Output is correct
29 Correct 2747 ms 63008 KB Output is correct
30 Correct 2891 ms 65452 KB Output is correct
31 Correct 3147 ms 70440 KB Output is correct
32 Correct 36 ms 13488 KB Output is correct
33 Correct 117 ms 20484 KB Output is correct
34 Correct 129 ms 20288 KB Output is correct
35 Correct 152 ms 20656 KB Output is correct
36 Correct 10 ms 12108 KB Output is correct
37 Correct 120 ms 20400 KB Output is correct
38 Correct 113 ms 19908 KB Output is correct
39 Correct 112 ms 20124 KB Output is correct
40 Correct 149 ms 19788 KB Output is correct
41 Correct 117 ms 20424 KB Output is correct
42 Correct 116 ms 20176 KB Output is correct
43 Correct 161 ms 20124 KB Output is correct
44 Correct 2868 ms 65452 KB Output is correct
45 Correct 2628 ms 69764 KB Output is correct
46 Correct 2438 ms 66396 KB Output is correct
47 Correct 1930 ms 69236 KB Output is correct
48 Correct 2886 ms 62696 KB Output is correct
49 Correct 2905 ms 65484 KB Output is correct
50 Correct 3019 ms 70404 KB Output is correct
51 Correct 3533 ms 82624 KB Output is correct
52 Correct 4066 ms 99008 KB Output is correct
53 Correct 3753 ms 100696 KB Output is correct
54 Correct 1918 ms 61504 KB Output is correct
55 Execution timed out 6076 ms 147324 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #5
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 13492 KB Output is correct
2 Correct 120 ms 20820 KB Output is correct
3 Correct 153 ms 20416 KB Output is correct
4 Correct 185 ms 20680 KB Output is correct
5 Correct 9 ms 12192 KB Output is correct
6 Correct 102 ms 20316 KB Output is correct
7 Correct 42 ms 13484 KB Output is correct
8 Correct 106 ms 20508 KB Output is correct
9 Correct 106 ms 20388 KB Output is correct
10 Correct 140 ms 20684 KB Output is correct
11 Correct 8 ms 12108 KB Output is correct
12 Correct 111 ms 20420 KB Output is correct
13 Correct 126 ms 19860 KB Output is correct
14 Correct 105 ms 20084 KB Output is correct
15 Correct 97 ms 19780 KB Output is correct
16 Correct 119 ms 20348 KB Output is correct
17 Correct 106 ms 20140 KB Output is correct
18 Correct 130 ms 20092 KB Output is correct
19 Correct 8 ms 11980 KB Output is correct
20 Correct 8 ms 12008 KB Output is correct
21 Correct 7 ms 11980 KB Output is correct
22 Correct 36 ms 13620 KB Output is correct
23 Correct 149 ms 20600 KB Output is correct
24 Correct 107 ms 20412 KB Output is correct
25 Correct 174 ms 20732 KB Output is correct
26 Correct 10 ms 12192 KB Output is correct
27 Correct 133 ms 20420 KB Output is correct
28 Correct 99 ms 19952 KB Output is correct
29 Correct 103 ms 20140 KB Output is correct
30 Correct 107 ms 19808 KB Output is correct
31 Correct 135 ms 20304 KB Output is correct
32 Correct 142 ms 20180 KB Output is correct
33 Correct 116 ms 20192 KB Output is correct
34 Correct 2985 ms 66860 KB Output is correct
35 Correct 3024 ms 63044 KB Output is correct
36 Correct 3225 ms 63108 KB Output is correct
37 Correct 2789 ms 67696 KB Output is correct
38 Correct 2533 ms 65496 KB Output is correct
39 Correct 2429 ms 63396 KB Output is correct
40 Correct 2865 ms 63648 KB Output is correct
41 Correct 2701 ms 62516 KB Output is correct
42 Correct 2969 ms 65340 KB Output is correct
43 Correct 2837 ms 69524 KB Output is correct
44 Correct 3138 ms 69752 KB Output is correct
45 Correct 2951 ms 65448 KB Output is correct
46 Correct 2716 ms 103624 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 13492 KB Output is correct
2 Correct 120 ms 20820 KB Output is correct
3 Correct 153 ms 20416 KB Output is correct
4 Correct 185 ms 20680 KB Output is correct
5 Correct 9 ms 12192 KB Output is correct
6 Correct 102 ms 20316 KB Output is correct
7 Correct 42 ms 13484 KB Output is correct
8 Correct 106 ms 20508 KB Output is correct
9 Correct 106 ms 20388 KB Output is correct
10 Correct 140 ms 20684 KB Output is correct
11 Correct 8 ms 12108 KB Output is correct
12 Correct 111 ms 20420 KB Output is correct
13 Correct 126 ms 19860 KB Output is correct
14 Correct 105 ms 20084 KB Output is correct
15 Correct 97 ms 19780 KB Output is correct
16 Correct 119 ms 20348 KB Output is correct
17 Correct 106 ms 20140 KB Output is correct
18 Correct 130 ms 20092 KB Output is correct
19 Correct 36 ms 13380 KB Output is correct
20 Correct 115 ms 20620 KB Output is correct
21 Correct 119 ms 20392 KB Output is correct
22 Correct 151 ms 20676 KB Output is correct
23 Correct 9 ms 12108 KB Output is correct
24 Correct 116 ms 20520 KB Output is correct
25 Correct 102 ms 19948 KB Output is correct
26 Correct 104 ms 20140 KB Output is correct
27 Correct 118 ms 19892 KB Output is correct
28 Correct 146 ms 20296 KB Output is correct
29 Correct 116 ms 20184 KB Output is correct
30 Correct 108 ms 20164 KB Output is correct
31 Correct 2611 ms 65504 KB Output is correct
32 Correct 2783 ms 69912 KB Output is correct
33 Correct 2418 ms 66472 KB Output is correct
34 Correct 2021 ms 69296 KB Output is correct
35 Correct 2747 ms 63008 KB Output is correct
36 Correct 2891 ms 65452 KB Output is correct
37 Correct 3147 ms 70440 KB Output is correct
38 Correct 8 ms 11980 KB Output is correct
39 Correct 8 ms 12008 KB Output is correct
40 Correct 7 ms 11980 KB Output is correct
41 Correct 36 ms 13620 KB Output is correct
42 Correct 149 ms 20600 KB Output is correct
43 Correct 107 ms 20412 KB Output is correct
44 Correct 174 ms 20732 KB Output is correct
45 Correct 10 ms 12192 KB Output is correct
46 Correct 133 ms 20420 KB Output is correct
47 Correct 99 ms 19952 KB Output is correct
48 Correct 103 ms 20140 KB Output is correct
49 Correct 107 ms 19808 KB Output is correct
50 Correct 135 ms 20304 KB Output is correct
51 Correct 142 ms 20180 KB Output is correct
52 Correct 116 ms 20192 KB Output is correct
53 Correct 2985 ms 66860 KB Output is correct
54 Correct 3024 ms 63044 KB Output is correct
55 Correct 3225 ms 63108 KB Output is correct
56 Correct 2789 ms 67696 KB Output is correct
57 Correct 2533 ms 65496 KB Output is correct
58 Correct 2429 ms 63396 KB Output is correct
59 Correct 2865 ms 63648 KB Output is correct
60 Correct 2701 ms 62516 KB Output is correct
61 Correct 2969 ms 65340 KB Output is correct
62 Correct 2837 ms 69524 KB Output is correct
63 Correct 3138 ms 69752 KB Output is correct
64 Correct 2951 ms 65448 KB Output is correct
65 Correct 2716 ms 103624 KB Output is correct
66 Correct 8 ms 11980 KB Output is correct
67 Correct 7 ms 12056 KB Output is correct
68 Correct 7 ms 11992 KB Output is correct
69 Correct 37 ms 13980 KB Output is correct
70 Correct 125 ms 21544 KB Output is correct
71 Correct 115 ms 21296 KB Output is correct
72 Correct 150 ms 21628 KB Output is correct
73 Correct 10 ms 12108 KB Output is correct
74 Correct 125 ms 21316 KB Output is correct
75 Correct 106 ms 20788 KB Output is correct
76 Correct 114 ms 21152 KB Output is correct
77 Correct 98 ms 20788 KB Output is correct
78 Correct 134 ms 21344 KB Output is correct
79 Correct 115 ms 21208 KB Output is correct
80 Correct 111 ms 21056 KB Output is correct
81 Correct 2711 ms 103908 KB Output is correct
82 Correct 2629 ms 108300 KB Output is correct
83 Correct 2503 ms 104936 KB Output is correct
84 Correct 1960 ms 107644 KB Output is correct
85 Correct 2617 ms 101320 KB Output is correct
86 Correct 2721 ms 103752 KB Output is correct
87 Correct 2864 ms 108628 KB Output is correct
88 Correct 2791 ms 104824 KB Output is correct
89 Correct 2949 ms 100748 KB Output is correct
90 Correct 2806 ms 99400 KB Output is correct
91 Correct 2600 ms 103772 KB Output is correct
92 Correct 3024 ms 101408 KB Output is correct
93 Correct 2585 ms 99596 KB Output is correct
94 Correct 3189 ms 100124 KB Output is correct
95 Correct 2753 ms 98572 KB Output is correct
96 Correct 2888 ms 101720 KB Output is correct
97 Correct 3084 ms 105184 KB Output is correct
98 Correct 2860 ms 105684 KB Output is correct
99 Correct 3220 ms 101744 KB Output is correct
100 Correct 3204 ms 102088 KB Output is correct
101 Correct 3062 ms 104048 KB Output is correct
102 Correct 2760 ms 104348 KB Output is correct
103 Correct 3169 ms 101968 KB Output is correct
104 Execution timed out 6009 ms 103092 KB Time limit exceeded
105 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 13492 KB Output is correct
2 Correct 120 ms 20820 KB Output is correct
3 Correct 153 ms 20416 KB Output is correct
4 Correct 185 ms 20680 KB Output is correct
5 Correct 9 ms 12192 KB Output is correct
6 Correct 102 ms 20316 KB Output is correct
7 Correct 42 ms 13484 KB Output is correct
8 Correct 106 ms 20508 KB Output is correct
9 Correct 106 ms 20388 KB Output is correct
10 Correct 140 ms 20684 KB Output is correct
11 Correct 8 ms 12108 KB Output is correct
12 Correct 111 ms 20420 KB Output is correct
13 Correct 126 ms 19860 KB Output is correct
14 Correct 105 ms 20084 KB Output is correct
15 Correct 97 ms 19780 KB Output is correct
16 Correct 119 ms 20348 KB Output is correct
17 Correct 106 ms 20140 KB Output is correct
18 Correct 130 ms 20092 KB Output is correct
19 Correct 36 ms 13380 KB Output is correct
20 Correct 115 ms 20620 KB Output is correct
21 Correct 119 ms 20392 KB Output is correct
22 Correct 151 ms 20676 KB Output is correct
23 Correct 9 ms 12108 KB Output is correct
24 Correct 116 ms 20520 KB Output is correct
25 Correct 102 ms 19948 KB Output is correct
26 Correct 104 ms 20140 KB Output is correct
27 Correct 118 ms 19892 KB Output is correct
28 Correct 146 ms 20296 KB Output is correct
29 Correct 116 ms 20184 KB Output is correct
30 Correct 108 ms 20164 KB Output is correct
31 Correct 2611 ms 65504 KB Output is correct
32 Correct 2783 ms 69912 KB Output is correct
33 Correct 2418 ms 66472 KB Output is correct
34 Correct 2021 ms 69296 KB Output is correct
35 Correct 2747 ms 63008 KB Output is correct
36 Correct 2891 ms 65452 KB Output is correct
37 Correct 3147 ms 70440 KB Output is correct
38 Correct 36 ms 13488 KB Output is correct
39 Correct 117 ms 20484 KB Output is correct
40 Correct 129 ms 20288 KB Output is correct
41 Correct 152 ms 20656 KB Output is correct
42 Correct 10 ms 12108 KB Output is correct
43 Correct 120 ms 20400 KB Output is correct
44 Correct 113 ms 19908 KB Output is correct
45 Correct 112 ms 20124 KB Output is correct
46 Correct 149 ms 19788 KB Output is correct
47 Correct 117 ms 20424 KB Output is correct
48 Correct 116 ms 20176 KB Output is correct
49 Correct 161 ms 20124 KB Output is correct
50 Correct 2868 ms 65452 KB Output is correct
51 Correct 2628 ms 69764 KB Output is correct
52 Correct 2438 ms 66396 KB Output is correct
53 Correct 1930 ms 69236 KB Output is correct
54 Correct 2886 ms 62696 KB Output is correct
55 Correct 2905 ms 65484 KB Output is correct
56 Correct 3019 ms 70404 KB Output is correct
57 Correct 3533 ms 82624 KB Output is correct
58 Correct 4066 ms 99008 KB Output is correct
59 Correct 3753 ms 100696 KB Output is correct
60 Correct 1918 ms 61504 KB Output is correct
61 Execution timed out 6076 ms 147324 KB Time limit exceeded
62 Halted 0 ms 0 KB -