oj.uz

Submission #406217

# Submission time Handle Problem Language Result Execution time Memory
406217 2021-05-17T09:35:43 Z tqbfjotld From Hacks to Snitches (BOI21_watchmen) C++14
15 / 100
 858 ms 152284 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

int special[250005];
vector<pair<int,int> > orig;
vector<int> routes[2755];
int cnt = 1;
vector<int> nodes[250005];

vector<int> new_adjl[250005];
int dist[250005];
int dist2[250005];
int tt[250005];
pair<int,int> rev[250005];

 main(){
    int n,m;
    scanf("%lld%lld",&n,&m);
    for (int x = 0; x<m; x++){
        int a,b;
        scanf("%lld%lld",&a,&b);
        orig.push_back({a,b});
    }
    int K;
    scanf("%lld",&K);
    for (int x = 0; x<K; x++){
        int l;
        scanf("%lld",&l);
        vector<int> stuff;
        for (int y = 0; y<l; y++){
            int a;
            scanf("%lld",&a);
            stuff.push_back(a);
            special[a] = l;
            tt[a] = y;
        }
    }
    for (int x = 1; x<=n; x++){
            for (int y = 0; y<special[x]; y++){
                rev[cnt] = {y,special[x]};
                dist2[cnt] = 999999999;
                nodes[x].push_back(cnt++);

            }
            if (special[x]==0){
                rev[cnt] = {0,0};
                dist2[cnt] = 999999999;
                nodes[x].push_back(cnt++);
            }

    }
    for (auto x : orig){
        if (special[x.first]&&special[x.second]){
            int l = special[x.first];
            for (int t = 0; t<l; t++){
                if (tt[x.first]!=t && tt[x.second]!=(t+1)%l &&
                        (!(tt[x.first]==(t+1)%l && tt[x.second]==t)))
                    new_adjl[nodes[x.first][t]].push_back(nodes[x.second][(t+1)%l]);
                if (tt[x.second]!=t && tt[x.first]!=(t+1)%l &&
                        (!(tt[x.second]==(t+1)%l && tt[x.first]==t)))
                    new_adjl[nodes[x.second][t]].push_back(nodes[x.first][(t+1)%l]);
            }
        }
        else if (special[x.first]){
            int l = special[x.first];
            for (int t = 0; t<l; t++){
                if (tt[x.first]!=t) new_adjl[nodes[x.first][t]].push_back(nodes[x.second][0]);
                if (tt[x.first]!=(t+1)%l) new_adjl[nodes[x.second][0]].push_back(nodes[x.first][(t+1)%l]);
            }
        }
        else if (special[x.second]){
            int l = special[x.second];
            for (int t = 0; t<l; t++){
                if (tt[x.second]!=(t+1)%l) new_adjl[nodes[x.first][0]].push_back(nodes[x.second][(t+1)%l]);
                if (tt[x.second]!=t) new_adjl[nodes[x.second][t]].push_back(nodes[x.first][0]);
            }
        }
        else{
            new_adjl[nodes[x.first][0]].push_back(nodes[x.second][0]);
            new_adjl[nodes[x.second][0]].push_back(nodes[x.first][0]);
        }
    }
    for (int x = 1; x<=n; x++){
        if (special[x]){
            for (int t = 0; t<special[x]; t++){
                if (t==tt[x]) continue;
                if ((t+1)%special[x]==tt[x]) continue;
                new_adjl[nodes[x][t]].push_back(nodes[x][(t+1)%special[x]]);
            }
        }
    }
    memset(dist,-1,sizeof(dist));
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    q.push({0,nodes[1][0]});
    while (!q.empty()){
        int node = q.top().second;
        int d = q.top().first;
        q.pop();
        if (dist[node]!=-1) continue;
        if (rev[node].second){
            if (d%rev[node].second!=rev[node].first){
                int del = (rev[node].first-d)%rev[node].second;
                if (del<0) del += rev[node].second;
                d += del;
                q.push({d,node});
                continue;
            }
        }
        //printf("node %lld, %lld\n",node,d);
        dist[node] = d;
        for (auto x : new_adjl[node]){
            if (d+1<dist2[x]){
                q.push({d+1,x});
                dist2[x] = d+1;
            }
        }
    }
    int ans = dist[nodes[n][0]];
    printf(ans==-1?"impossible":"%lld",ans);
}

Compilation message

watchmen.cpp:17:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   17 |  main(){
      |  ^~~~
watchmen.cpp: In function 'int main()':
watchmen.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%lld%lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
watchmen.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%lld%lld",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
watchmen.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%lld",&K);
      |     ~~~~~^~~~~~~~~~~
watchmen.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%lld",&l);
      |         ~~~~~^~~~~~~~~~~
watchmen.cpp:33:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |             scanf("%lld",&a);
      |             ~~~~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 117168 KB Output is correct
2 Correct 110 ms 26168 KB Output is correct
3 Correct 109 ms 26300 KB Output is correct
4 Correct 204 ms 61552 KB Output is correct
5 Correct 13 ms 15308 KB Output is correct
6 Correct 109 ms 26244 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 117180 KB Output is correct
2 Correct 107 ms 26076 KB Output is correct
3 Correct 107 ms 26268 KB Output is correct
4 Correct 200 ms 61696 KB Output is correct
5 Correct 16 ms 15180 KB Output is correct
6 Correct 117 ms 26240 KB Output is correct
7 Correct 125 ms 25136 KB Output is correct
8 Correct 110 ms 24928 KB Output is correct
9 Correct 100 ms 24624 KB Output is correct
10 Correct 159 ms 35380 KB Output is correct
11 Correct 130 ms 28312 KB Output is correct
12 Correct 103 ms 25264 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 117180 KB Output is correct
2 Correct 107 ms 26076 KB Output is correct
3 Correct 107 ms 26268 KB Output is correct
4 Correct 200 ms 61696 KB Output is correct
5 Correct 16 ms 15180 KB Output is correct
6 Correct 117 ms 26240 KB Output is correct
7 Correct 125 ms 25136 KB Output is correct
8 Correct 110 ms 24928 KB Output is correct
9 Correct 100 ms 24624 KB Output is correct
10 Correct 159 ms 35380 KB Output is correct
11 Correct 130 ms 28312 KB Output is correct
12 Correct 103 ms 25264 KB Output is correct
13 Correct 231 ms 117232 KB Output is correct
14 Correct 113 ms 26160 KB Output is correct
15 Correct 122 ms 26200 KB Output is correct
16 Correct 198 ms 61616 KB Output is correct
17 Correct 13 ms 15308 KB Output is correct
18 Correct 126 ms 26320 KB Output is correct
19 Correct 113 ms 25120 KB Output is correct
20 Correct 123 ms 24924 KB Output is correct
21 Correct 101 ms 24644 KB Output is correct
22 Correct 152 ms 35428 KB Output is correct
23 Correct 135 ms 28348 KB Output is correct
24 Correct 104 ms 25272 KB Output is correct
25 Runtime error 858 ms 152224 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 117180 KB Output is correct
2 Correct 107 ms 26076 KB Output is correct
3 Correct 107 ms 26268 KB Output is correct
4 Correct 200 ms 61696 KB Output is correct
5 Correct 16 ms 15180 KB Output is correct
6 Correct 117 ms 26240 KB Output is correct
7 Correct 125 ms 25136 KB Output is correct
8 Correct 110 ms 24928 KB Output is correct
9 Correct 100 ms 24624 KB Output is correct
10 Correct 159 ms 35380 KB Output is correct
11 Correct 130 ms 28312 KB Output is correct
12 Correct 103 ms 25264 KB Output is correct
13 Correct 231 ms 117232 KB Output is correct
14 Correct 113 ms 26160 KB Output is correct
15 Correct 122 ms 26200 KB Output is correct
16 Correct 198 ms 61616 KB Output is correct
17 Correct 13 ms 15308 KB Output is correct
18 Correct 126 ms 26320 KB Output is correct
19 Correct 113 ms 25120 KB Output is correct
20 Correct 123 ms 24924 KB Output is correct
21 Correct 101 ms 24644 KB Output is correct
22 Correct 152 ms 35428 KB Output is correct
23 Correct 135 ms 28348 KB Output is correct
24 Correct 104 ms 25272 KB Output is correct
25 Runtime error 858 ms 152224 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 117168 KB Output is correct
2 Correct 110 ms 26168 KB Output is correct
3 Correct 109 ms 26300 KB Output is correct
4 Correct 204 ms 61552 KB Output is correct
5 Correct 13 ms 15308 KB Output is correct
6 Correct 109 ms 26244 KB Output is correct
7 Correct 235 ms 117180 KB Output is correct
8 Correct 107 ms 26076 KB Output is correct
9 Correct 107 ms 26268 KB Output is correct
10 Correct 200 ms 61696 KB Output is correct
11 Correct 16 ms 15180 KB Output is correct
12 Correct 117 ms 26240 KB Output is correct
13 Correct 125 ms 25136 KB Output is correct
14 Correct 110 ms 24928 KB Output is correct
15 Correct 100 ms 24624 KB Output is correct
16 Correct 159 ms 35380 KB Output is correct
17 Correct 130 ms 28312 KB Output is correct
18 Correct 103 ms 25264 KB Output is correct
19 Correct 11 ms 14028 KB Output is correct
20 Correct 9 ms 14028 KB Output is correct
21 Correct 10 ms 14028 KB Output is correct
22 Correct 233 ms 117800 KB Output is correct
23 Correct 122 ms 26832 KB Output is correct
24 Correct 153 ms 26956 KB Output is correct
25 Correct 227 ms 62384 KB Output is correct
26 Correct 14 ms 15308 KB Output is correct
27 Correct 111 ms 27112 KB Output is correct
28 Correct 115 ms 25860 KB Output is correct
29 Correct 100 ms 25724 KB Output is correct
30 Correct 95 ms 25340 KB Output is correct
31 Correct 156 ms 36092 KB Output is correct
32 Correct 118 ms 29104 KB Output is correct
33 Correct 104 ms 26112 KB Output is correct
34 Runtime error 828 ms 152284 KB Execution killed with signal 6
35 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 117168 KB Output is correct
2 Correct 110 ms 26168 KB Output is correct
3 Correct 109 ms 26300 KB Output is correct
4 Correct 204 ms 61552 KB Output is correct
5 Correct 13 ms 15308 KB Output is correct
6 Correct 109 ms 26244 KB Output is correct
7 Correct 235 ms 117180 KB Output is correct
8 Correct 107 ms 26076 KB Output is correct
9 Correct 107 ms 26268 KB Output is correct
10 Correct 200 ms 61696 KB Output is correct
11 Correct 16 ms 15180 KB Output is correct
12 Correct 117 ms 26240 KB Output is correct
13 Correct 125 ms 25136 KB Output is correct
14 Correct 110 ms 24928 KB Output is correct
15 Correct 100 ms 24624 KB Output is correct
16 Correct 159 ms 35380 KB Output is correct
17 Correct 130 ms 28312 KB Output is correct
18 Correct 103 ms 25264 KB Output is correct
19 Correct 231 ms 117232 KB Output is correct
20 Correct 113 ms 26160 KB Output is correct
21 Correct 122 ms 26200 KB Output is correct
22 Correct 198 ms 61616 KB Output is correct
23 Correct 13 ms 15308 KB Output is correct
24 Correct 126 ms 26320 KB Output is correct
25 Correct 113 ms 25120 KB Output is correct
26 Correct 123 ms 24924 KB Output is correct
27 Correct 101 ms 24644 KB Output is correct
28 Correct 152 ms 35428 KB Output is correct
29 Correct 135 ms 28348 KB Output is correct
30 Correct 104 ms 25272 KB Output is correct
31 Runtime error 858 ms 152224 KB Execution killed with signal 6
32 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 117168 KB Output is correct
2 Correct 110 ms 26168 KB Output is correct
3 Correct 109 ms 26300 KB Output is correct
4 Correct 204 ms 61552 KB Output is correct
5 Correct 13 ms 15308 KB Output is correct
6 Correct 109 ms 26244 KB Output is correct
7 Correct 235 ms 117180 KB Output is correct
8 Correct 107 ms 26076 KB Output is correct
9 Correct 107 ms 26268 KB Output is correct
10 Correct 200 ms 61696 KB Output is correct
11 Correct 16 ms 15180 KB Output is correct
12 Correct 117 ms 26240 KB Output is correct
13 Correct 125 ms 25136 KB Output is correct
14 Correct 110 ms 24928 KB Output is correct
15 Correct 100 ms 24624 KB Output is correct
16 Correct 159 ms 35380 KB Output is correct
17 Correct 130 ms 28312 KB Output is correct
18 Correct 103 ms 25264 KB Output is correct
19 Correct 231 ms 117232 KB Output is correct
20 Correct 113 ms 26160 KB Output is correct
21 Correct 122 ms 26200 KB Output is correct
22 Correct 198 ms 61616 KB Output is correct
23 Correct 13 ms 15308 KB Output is correct
24 Correct 126 ms 26320 KB Output is correct
25 Correct 113 ms 25120 KB Output is correct
26 Correct 123 ms 24924 KB Output is correct
27 Correct 101 ms 24644 KB Output is correct
28 Correct 152 ms 35428 KB Output is correct
29 Correct 135 ms 28348 KB Output is correct
30 Correct 104 ms 25272 KB Output is correct
31 Runtime error 858 ms 152224 KB Execution killed with signal 6
32 Halted 0 ms 0 KB -