Submission #427697

#	Time	Username	Problem	Language	Result	Execution time	Memory
427697		duality	From Hacks to Snitches (BOI21_watchmen)	C++11	100 / 100	4301 ms	239724 KiB

watchmen

#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];
set<pii> done3[250000];
map<int,int> done4[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);
        if (done[u] && (dist[u][(d+p[u].first-1) % p[u].first] == d-1)) continue;
        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 {
                done4[v][p[u].second.second]++;
                if (done4[v][p[u].second.second] >= 30) continue;
                if (done3[v].count(mp(d % p[v].first,p[u].first))) continue;
                vector<LLI> dd(p[v].first,-1);
                priority_queue<LLI> H2;
                for (j = 0; j < ((((p[u].second.first-d) % p[u].first)+p[u].first) % p[u].first); j++) {
                    if (j == p[v].first) break;
                    dd[(d+j) % p[v].first] = d+j;
                }
                for (j = 0; j < p[v].first; j++) {
                    if (dd[j] != -1) H2.push(-dd[j]);
                }
                while (!H2.empty()) {
                    LLI d = -H2.top();
                    H2.pop();

                    if (d > dd[d % p[v].first]) continue;
                    if ((dd[(d+p[u].first) % p[v].first] == -1) || (d+p[u].first < dd[(d+p[u].first) % p[v].first])) {
                        dd[(d+p[u].first) % p[v].first] = d+p[u].first;
                        H2.push(-(d+p[u].first));
                    }
                }
                for (j = 0; j < p[v].first; j++) {
                    if (dd[j] != -1) {
                        LLI d2 = dd[j]+1;
                        if ((d2 % p[v].first) != p[v].second.first) relax(v,d2);
                    }
                }
                done3[v].insert(mp(d % p[v].first,p[u].first));
            }
        }
        done[u] = 1;
    }
    printf("impossible\n");

    return 0;
}

Compilation message (stderr)

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

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