Submission #658707

#	Time	Username	Problem	Language	Result	Execution time	Memory
658707		Lobo	From Hacks to Snitches (BOI21_watchmen)	C++17	0 / 100	433 ms	505204 KiB

watchmen

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()

const int inf = 1e9+10;
const int maxn = 3e5+10;
const int maxd = 1e7;

int n, m, k;
int szrt[maxn], idrt[maxn], thrt[maxn], isrt[maxn], nxrt[maxn], pvrt[maxn], dlol[maxn];
vector<int> g[maxn], d[maxn];
vector<pair<int,pair<int,int>>> withdist[maxd+1];

int32_t main() {
    freopen("in.in", "r", stdin);

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u,v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    cin >> k;
    for(int i = 1; i <= k; i++) {
        cin >> szrt[i];
        for(int j = 0; j < szrt[i]; j++) {
            int v; cin >> v;
            idrt[v] = i;
            isrt[v] = 1;
            thrt[v] = j;
        }
    }

    szrt[0] = 1;
    for(int i = 1; i <= n; i++) {
        dlol[i] = inf;
        if(isrt[i]) {
            for(int j = 0; j < szrt[idrt[i]]; j++) {
                d[i].pb(inf);
            }
            int u = i;
            for(auto v : g[u]) {
                if(isrt[v] && idrt[u] == idrt[v] && thrt[v] == (thrt[u]+1)%szrt[idrt[u]]) {
                    nxrt[u] = v;
                }
                if(isrt[v] && idrt[u] == idrt[v] && thrt[u] == (thrt[v]+1)%szrt[idrt[u]]) {
                    pvrt[u] = v;
                }
            }
        }
        else {
            d[i].pb(inf);
        }

    }

    d[1][0] = 0;
    priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> pq;
    pq.push(mp(0,mp(1,0)));
    withdist[0].pb(mp(0,mp(1,0)));
    for(int distcur = 0; distcur <= maxd; distcur++) {
    while(withdist[distcur].size()) {
        auto X = withdist[distcur].back();
        withdist[distcur].pop_back();
        int u = X.sc.fr;
        int t = X.sc.sc;
        int dist = X.fr;
    // while(pq.size()) {
    //     int u = pq.top().sc.fr;
    //     int t = pq.top().sc.sc;
    //     int dist = pq.top().fr;
    //     pq.pop();

        if(t != -1 && dist != d[u][t]) continue;
        if(t == -1 && dist != dlol[u]) continue;

        if(t == -1) {
            for(auto v : g[u]) {
                if(isrt[v]) {
                    int d1 = dlol[u]+1;
                    int t1 = d1%szrt[idrt[v]];
                    // Vou encontrar o guarda em v ou indo para v
                    // indo para v == u é depois de v e em t1 ele vai estar em u
                    if(t1 == thrt[v] || (thrt[u] == (thrt[v]+1)%szrt[idrt[u]] && t1 == thrt[u]) && idrt[u] == idrt[v]) continue;
                    if(d[v][t1] > d1) {
                        d[v][t1] = d1;
                        pq.push(mp(d[v][t1],mp(v,t1)));
                        withdist[d[v][t1]].pb(mp(d[v][t1],mp(v,t1)));
                    }

                    if(idrt[v] != idrt[u]) {
                        set<int> stt1;
                        d1 = dlol[u]+1;
                        while(true) {
                            int t1 = d1%szrt[idrt[v]];
                            if(stt1.count(t1)) break;
                            stt1.insert(t1);
                            // Vou encontrar o guarda em v ou indo para v
                            // indo para v == u é depois de v e em t1 ele vai estar em u
                            if(d[v][t1] > d1 && t1 != thrt[v]) {
                                d[v][t1] = d1;
                                pq.push(mp(d[v][t1],mp(v,t1)));
                                withdist[d[v][t1]].pb(mp(d[v][t1],mp(v,t1)));
                            }
                            d1+= szrt[idrt[u]];
                        }
                    }
                }
                else {
                    int d1 = dlol[u]+1;
                    int t1 = 0;
                    if(d[v][t1] > d1) {
                        d[v][t1] = d1;
                        pq.push(mp(d[v][t1],mp(v,t1)));
                        withdist[d[v][t1]].pb(mp(d[v][t1],mp(v,t1)));
                    }
                }
            }
            continue;
        }

        if(isrt[u]) {
            int v,d1,t1;
            v = nxrt[u];
            d1 = d[u][t]+1;
            t1 = d1%szrt[idrt[v]];
            // Vou encontrar o guarda em v ou indo para v
            // indo para v == u é depois de v e em t1 ele vai estar em u
            if(!(t1 == thrt[v] || (thrt[u] == (thrt[v]+1)%szrt[idrt[u]] && t1 == thrt[u] && idrt[u] == idrt[v])) && d[v][t1] > d1) {
                d[v][t1] = d1;
                pq.push(mp(d[v][t1],mp(v,t1)));
                withdist[d[v][t1]].pb(mp(d[v][t1],mp(v,t1)));
            }

            v = pvrt[u];
            d1 = d[u][t]+1;
            t1 = d1%szrt[idrt[v]];
            // Vou encontrar o guarda em v ou indo para v
            // indo para v == u é depois de v e em t1 ele vai estar em u
            if(!(t1 == thrt[v] || (thrt[u] == (thrt[v]+1)%szrt[idrt[u]] && t1 == thrt[u] && idrt[u] == idrt[v])) && d[v][t1] > d1) {
                d[v][t1] = d1;
                pq.push(mp(d[v][t1],mp(v,t1)));
                withdist[d[v][t1]].pb(mp(d[v][t1],mp(v,t1)));
            }

            if(dlol[u] > d[u][t]) {
                dlol[u] = d[u][t];
                pq.push(mp(dlol[u],mp(u,-1)));
                withdist[dlol[u]].pb(mp(dlol[u],mp(u,-1)));
            }

            v = u;
            d1 = d[u][t]+1;
            t1 = d1%szrt[idrt[v]];
            if(!(t1 == thrt[v]) && d[v][t1] > d1) {
                d[v][t1] = d1;
                pq.push(mp(d[v][t1],mp(v,t1)));
                withdist[d[v][t1]].pb(mp(d[v][t1],mp(v,t1)));
            }
        }
        else {
            for(auto v : g[u]) {
                if(isrt[v]) {
                    // d[u][t]+1+i = (thrt[v]+1) MOD
                    // i = trrt[v]-d[u][t] MOD
                    int i = ((thrt[v]-d[u][t])%szrt[idrt[v]]+szrt[idrt[v]])%szrt[idrt[v]];
                    int d1 = d[u][t]+1+i;
                    int t1 = d1%szrt[idrt[v]];
                    if(t1 == thrt[v]) continue;
                    if(d[v][t1] > d1) {
                        d[v][t1] = d1;
                        pq.push(mp(d[v][t1],mp(v,t1)));
                        withdist[d[v][t1]].pb(mp(d[v][t1],mp(v,t1)));
                    }
                    d1 = d[u][t]+1;
                    t1 = d1%szrt[idrt[v]];
                    if(t1 == thrt[v]) continue;
                    if(d[v][t1] > d1) {
                        d[v][t1] = d1;
                        pq.push(mp(d[v][t1],mp(v,t1)));
                        withdist[d[v][t1]].pb(mp(d[v][t1],mp(v,t1)));
                    }
                }
                else {
                    int d1 = d[u][t]+1;
                    int t1 = 0;
                    if(d[v][t1] > d1) {
                        d[v][t1] = d1;
                        pq.push(mp(d[v][t1],mp(v,t1)));
                        withdist[d[v][t1]].pb(mp(d[v][t1],mp(v,t1)));
                    }
                }
            }
        }
    }
    }

    if(d[n][0] == inf) cout << "impossible" << endl;
    else cout << d[n][0] << endl;
}

Compilation message (stderr)

watchmen.cpp: In function 'int32_t main()':
watchmen.cpp:90:97: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   90 |                     if(t1 == thrt[v] || (thrt[u] == (thrt[v]+1)%szrt[idrt[u]] && t1 == thrt[u]) && idrt[u] == idrt[v]) continue;
      |                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
watchmen.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen("in.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• 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