Submission #1224585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224585		KALARRY	From Hacks to Snitches (BOI21_watchmen)	C++20	0 / 100	37 ms	10056 KiB

watchmen

//chockolateman

#include<bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int N,M,K,dist[250005];
vector<int> adj[250005];
pair<int,int> prohibited[250005]; //a mod b
bool visited[250005];

void Dijsktra(int start)
{
    for(int i = 1 ; i <= N ; i++)
        dist[i] = INF;
    dist[start] = 0;
    priority_queue<pair<int,int>> q;
    q.push({0,start});
    while(!q.empty())
    {
        int v = q.top().second;
        q.pop();
        if(visited[v])
            continue;
        visited[v] = true;
        for(auto u : adj[v])
        {
            int w = 1;
            if(prohibited[u].second && ((dist[v] + 1)%prohibited[u].second) == prohibited[u].first)
                w++;
            if(dist[v] + w < dist[u])
            {
                dist[u] = dist[v] + w;
                q.push({-dist[u],u});
            }
        }
    }
}

int main()
{
    scanf("%d%d",&N,&M);
    for(int a,b,i = 1 ; i <= M ; i++)
    {
        scanf("%d%d",&a,&b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    scanf("%d",&K);
    for(int s,i = 1 ; i <= K ; i++)
    {
        scanf("%d",&s);
        for(int l,j = 0 ; j < s ; j++)
        {
            scanf("%d",&l);
            prohibited[l] = {j,s};
        }
    }
    Dijsktra(1);
    printf("%d\n",dist[N]);
    return 0;
}

Compilation message (stderr)

watchmen.cpp: In function 'int main()':
watchmen.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d%d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~
watchmen.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~
watchmen.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d",&K);
      |     ~~~~~^~~~~~~~~
watchmen.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%d",&s);
      |         ~~~~~^~~~~~~~~
watchmen.cpp:57:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |             scanf("%d",&l);
      |             ~~~~~^~~~~~~~~

• 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