Submission #751610

#	Time	Username	Problem	Language	Result	Execution time	Memory
751610		lohacho	From Hacks to Snitches (BOI21_watchmen)	C++14	100 / 100	5717 ms	240596 KiB

watchmen

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;

const int NS = 250004;

int n, m;
vector<int> way[NS];
vector<int> dp[NS];
int len[NS], fir[NS], col[NS];

struct Data{
    int x, t;
    Data(){}
    Data(int x, int t):x(x), t(t){}
    bool operator<(const Data&r)const{
        return t > r.t;
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        int x, y;
        cin >> x >> y;
        --x, --y;
        way[x].push_back(y);
        way[y].push_back(x);
    }

    int k;
    cin >> k;
    for(int i = 0; i < k; ++i){
        int x;
        cin >> x;
        for(int j = 0; j < x; ++j){
            int y;
            cin >> y;
            --y;
            dp[y] = vector<int>(x, (int)1e9);
            len[y] = x;
            col[y] = i + 1;
            fir[y] = j;
        }
    }

    for(int i = 0; i < n; ++i){
        if(!(int)dp[i].size()){
            dp[i] = {(int)1e9};
        }
    }

    priority_queue<Data> pq;

    auto enq = [&](int x, int t){
        int md = (col[x] ? t % len[x] : 0);
        if((!col[x] || md != fir[x]) && t < dp[x][md]){
            pq.push(Data(x, t));
        }
    };

    auto gett = [&](int x, int t){
        if(t <= fir[x]) return fir[x];
        return ((t - fir[x] - 1) / len[x] + 1) * len[x] + fir[x];
    };

    enq(0, 0);
    while(!pq.empty()){
        int now = pq.top().x;
        int nt = pq.top().t;
        pq.pop();

        int md = (col[now] ? nt % len[now] : 0);
        if(dp[now][md] == nt){
            continue;
        }
        if(now == n - 1){
            cout << nt << '\n';
            return 0;
        }
        //cout << now + 1 << ' ' << nt << endl;

        dp[now][md] = nt;
        enq(now, nt + 1);
        for(int i = 0; i < (int)way[now].size(); ++i){
            int nxt = way[now][i];
            int f = 0;
            if(!col[now] || !(col[now] == col[nxt] && fir[now] == (fir[nxt] + 1) % len[now] && fir[nxt] == nt % len[now])){
                enq(nxt, nt + 1);
            }
            if((!col[now] && col[nxt]) || (col[now] && col[now] == col[nxt] && fir[now] != (fir[nxt] + 1) % len[now] && fir[nxt] != (fir[now] + 1) % len[nxt])){
                enq(nxt, gett(nxt, nt) + 1); f = 1;
            }
            if(col[now] && col[nxt] && col[now] != col[nxt]){
                int t2 = gett(nxt, nt);
                int t1 = gett(now, t2);
                if(t1 != t2){
                    enq(nxt, t2 + 1);
                    f = 1;
                }
                else{
                    int t3 = t1 + (len[now] * 2 - fir[now] + md) % len[now];
                    int t4 = gett(nxt, t3);
                    enq(nxt, t3 + 1);
                    if(gett(now, t4) != t4){
                        enq(nxt, t4 + 1);
                    }
                }
            }

            if(!col[now] || !col[nxt] || f){
                swap(way[now][i], way[now].back());
                way[now].pop_back();
                --i;
            }
        }
    }

    cout << "impossible\n";

    return 0;
}

• 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