Submission #406227

#	Time	Username	Problem	Language	Result	Execution time	Memory
406227		tqbfjotld	From Hacks to Snitches (BOI21_watchmen)	C++14	15 / 100	2597 ms	524292 KiB

watchmen

#include <bits/stdc++.h>
using namespace std;


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

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

 main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for (int x = 0; x<m; x++){
        int a,b;
        scanf("%d%d",&a,&b);
        orig.push_back({a,b});
    }
    int K;
    scanf("%d",&K);
    for (int x = 0; x<K; x++){
        int l;
        scanf("%d",&l);
        vector<int> stuff;
        for (int y = 0; y<l; y++){
            int a;
            scanf("%d",&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":"%d",ans);
}

Compilation message (stderr)

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("%d%d",&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("%d%d",&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("%d",&K);
      |     ~~~~~^~~~~~~~~
watchmen.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%d",&l);
      |         ~~~~~^~~~~~~~~
watchmen.cpp:33:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |             scanf("%d",&a);
      |             ~~~~~^~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20