Submission #404102

#	Time	Username	Problem	Language	Result	Execution time	Memory
404102		doowey	From Hacks to Snitches (BOI21_watchmen)	C++14	0 / 100	112 ms	39008 KiB

watchmen

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 250111;
vector<int> T[N];
int idx[N];
int mod[N];
vector<int> ord[N];
vector<int> dp[N];
vector<bool> vis[N];
bool outit[N];
int qash[N];

struct item{
    ll dist;
    int p;
    int q;
    bool operator<(const item &pq) const {
        return pq.dist < dist;
    }
};

int main(){
    fastIO;
    int n, m;
    cin >> n >> m;
    int u, v;
    for(int i = 1; i <= m ; i ++ ){
        cin >> u >> v;
        T[u].push_back(v);
        T[v].push_back(u);
    }
    int k;
    cin >> k;
    int sz;
    for(int iq = 1; iq <= k; iq ++ ){
        cin >> sz;
        mod[iq] = sz ;
        for(int i = 1; i <= sz ; i ++ ){
            cin >> u;
            qash[u] = i - 1;
            idx[u] = iq;
            ord[iq].push_back(u);
        }
    }
    for(int i = 1; i <= n; i ++ ){
        if(idx[i] == 0){
            dp[i].resize(1,(int)1e9);
            vis[i].resize(1, false);
        }
        else{
            dp[i].resize(mod[idx[i]],(int)1e9);
            vis[i].resize(mod[idx[i]],false);
        }
    }
    dp[1][0] = 0;
    priority_queue<item> pq;
    pq.push({0, 1, 0});
    int node;
    int dis;
    int res;
    int nex;
    int ix;
    int ban0, ban1;
    while(!pq.empty()){
        node = pq.top().p;
        res = pq.top().q;
        dis = pq.top().dist;
        pq.pop();
        if(vis[node][res]) continue;
        vis[node][res]=true;
        if(idx[node] == 0){
            for(auto x : T[node]){
                if(idx[x] == 0){
                    if(dp[x][0] > dis + 1){
                        dp[x][0] = dis + 1;
                        pq.push({dis + 1, x, 0});
                    }
                }
                else{
                    for(int j = 1; j <= mod[idx[x]]; j ++ ){
                        nex = (dis + j) % mod[idx[x]];
                        if(ord[idx[x]][nex] != x){
                            if(dp[x][nex] > dis + j){
                                dp[x][nex] = dis + j;
                                pq.push({dis + j, x, nex});
                            }
                        }
                    }
                }
            }
        }
        else{
            if(!outit[node]){
                outit[node]=true;
                for(auto x : T[node]){
                    if(idx[x] == 0){
                        if(dp[x][0] > dis + 1){
                            dp[x][0] = dis + 1;
                            pq.push({dis + 1, x, 0});
                        }
                    }
                }
            }
            ix = qash[node];
            if(node != ord[idx[node]][(res + 1) % mod[idx[node]]]){
                if(dp[node][(res + 1) % mod[idx[node]]] > dis + 1){
                    dp[node][(res + 1) % mod[idx[node]]] = dis + 1;
                    pq.push({dis + 1, node, (res + 1) % mod[idx[node]]});
                }
            }
            nex = ord[idx[node]][(ix + 1) % mod[idx[node]]];
            if(dp[nex][(res + 1) % mod[idx[node]]] > dis + 1){
                dp[nex][(res + 1) % mod[idx[node]]] = dis + 1;
                pq.push({dis + 1, nex, (res + 1) % mod[idx[node]]});
            }
            ban0 = ord[idx[node]][res];
            ban1 = ord[idx[node]][(res + 1) % mod[idx[node]]];
            nex = ord[idx[node]][(ix - 1 + mod[idx[node]]) % mod[idx[node]]];
            if(nex != ban0 && nex != ban1 && dp[nex][(res + 1) % mod[idx[node]]] > dis + 1){
                dp[nex][(res + 1) % mod[idx[node]]] = dis + 1;
                pq.push({dis + 1, nex, (res + 1) % mod[idx[node]]});
            }
        }
    }
    if(dp[n][0] > (int)1e8)
        cout << "impossible\n";
    else
        cout << dp[n][0] << "\n";
    return 0;
}

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