Submission #1236590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236590		amine_aroua	From Hacks to Snitches (BOI21_watchmen)	C++20	0 / 100	61 ms	7492 KiB

watchmen

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
signed main()
{
    // if i am special , i wont go to a special
    // normal goes to a non updated special : 4 cases
    // - wait 1 or not
    // - go same dir
    // - or go reverse till collision
    // - wait , go reverse

    int n , m;
    cin>>n>>m;
    vector<vector<int>> adj(n + 1);
    for(int i = 0 ; i < m ; i++)
    {
        int u , v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int k;
    cin>>k;
    vector<vector<int>> seq(k);
    vector<int> belongs(n + 1 , -1);
    vector<int> order(n + 1);
    for(int i = 0 ; i < k ; i++)
    {
        int l;
        cin>>l;
        seq[i].assign(l , 0);
        for(int j= 0 ; j < l ; j++)
        {
            cin>>seq[i][j];
            order[seq[i][j]] = j;
            belongs[seq[i][j]] = i;
        }
    }
    vector<int> cand(n + 1 , INF);
    vector<bool> updated(n + 1);
    vector<bool> vis(n + 1);
    vector<int> dist(n + 1 , INF);
    priority_queue<pair<int ,int> , vector<pair<int ,int>> , greater<pair<int , int>>>pq;
    pq.push({0 , 1});
    dist[1] = 0;
    while(!pq.empty())
    {
        auto [d , tp] = pq.top();
        pq.pop();
        if(vis[tp])
            continue;
        vis[tp ] = 1;
        int orgd = d;
        for(auto u : adj[tp])
        {
            d = orgd;
            if(belongs[u] == -1)
            {
                if(dist[u] > d + 1)
                {
                    dist[u] = d + 1;
                    pq.push({d + 1 , u});
                }
            }
            else if(belongs[tp] == -1 && !updated[u])
            {
                int idx = belongs[u];
                int len = (int)seq[idx].size();
                int where = seq[idx][d%len];
                int wait = (order[u] - order[where] + len) % len +1;
                int bd = d;
                d++;
                where = seq[idx][d%len];
                if(where == u)
                {
                    d++;
                    where = seq[idx][d%len];
                }
                int pwhere = where;
                int pd = d;
                int h = order[u];
                int cur = u;
                // reverse till collision
                while(where != cur)
                {
                    cand[cur] = min(cand[cur] , d);
                    d++;
                    h--;
                    if(h < 0)
                        h+=len;
                    where = seq[idx][d%len];
                    if(where == cur)
                        break;
                    cur = seq[idx][h % len];
                }
                // reverse and wait

                h = order[u];
                d = (order[u] + 1)%len;
                cur = u;
                where = seq[idx][d];
                while(cur != where)
                {
                    cand[seq[idx][h]] = min(cand[seq[idx][h]] , wait);
                    wait++;
                    h--;
                    d++;
                    if(h < 0)
                        h+=len;
                    if(d == len)
                        d-=len;
                    where = seq[idx][d];
                    if(where == cur)
                        break;
                    cur = seq[idx][h];
                }

                //go same dir

                h = order[u];
                d= pd;
                for(int i = 0 ; i < len ; i++)
                {
                    cand[seq[idx][h]] = min(cand[seq[idx][h]] , d);
                    d++;
                    h++;
                    if(h == len)
                        h-=len;
                }
                updated[u] = 1;
                for(int i = 0 ; i < len ; i++)
                {
                    int node = seq[idx][i];
                    if(dist[node] > cand[node])
                    {
                        dist[node] = cand[node];
                        pq.push({dist[node] , node});
                    }
                }
            }
        }
    }
    cout<<(dist[n] == INF ? -1 : dist[n])<<'\n';
}   

• 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