Submission #426383

#	Time	Username	Problem	Language	Result	Execution time	Memory
426383		duality	From Hacks to Snitches (BOI21_watchmen)	C++11	25 / 100	6056 ms	135452 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;
int readInt() {
    char c;
    int n = 0;
    while ((c=getchar()) < '0');
    n = c-'0';
    while ((c=getchar()) >= '0') n = n*10+c-'0';
    return n;
}

vi adjList[250000];
int pos[250000];
pair<int,pii> p[250000];
bool comp(int a,int b) {
    return p[a] < p[b];
}
vi dist[250000];
int done[250000],done2[250000];
vi Q[1000000];
int main() {
    int i,j;
    int N,M,K;
    int u,v,l;
    scanf("%d %d",&N,&M);
    for (i = 0; i < M; i++) {
        u = readInt();
        v = readInt();
        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);
        sort(adjList[i].begin(),adjList[i].end(),comp);
        while ((pos[i] < adjList[i].size()) && (p[adjList[i][pos[i]]].first <= 1)) pos[i]++;
    }
    int pp = 0;
    dist[0][0] = 0,Q[0].pb(0);
    while (1) {
        while ((pp < 1000000) && (Q[pp].empty())) pp++;
        if (pp == 1000000) break;
        int u = Q[pp].back();
        int d = pp;
        Q[pp].pop_back();

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

    return 0;
}

Compilation message (stderr)

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:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (; i < adjList[u].size(); i++) {
      |                ~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
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: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20