Submission #51664

#	Time	Username	Problem	Language	Result	Execution time	Memory
51664		gs13105	철도 요금 (JOI16_ho_t3)	C++17	100 / 100	191 ms	15276 KiB

2016_ho_t3

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>

using namespace std;

struct edg
{
    int y, w;
};

int ori[200010][2];
int que[200010];
int num[200010];

vector<edg> arr[100010];
int dis[100010];
int mem[100010];
const int INF = 1e8;

int res[200010];

int main()
{
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);

    int n, m, q, i;
    scanf("%d%d%d", &n, &m, &q);
    for(i = 1; i <= m; i++)
        scanf("%d%d", &ori[i][0], &ori[i][1]);
    for(i = 1; i <= q; i++)
        scanf("%d", &que[i]);

    for(i = 1; i <= m; i++)
        num[i] = INF;
    for(i = 1; i <= q; i++)
        num[que[i]] = i;

    for(i = 1; i <= m; i++)
    {
        int x = ori[i][0];
        int y = ori[i][1];
        int w = num[i];

        arr[x].push_back({ y, w });
        arr[y].push_back({ x, w });
    }

    dis[1] = 0;
    for(i = 2; i <= n; i++)
        dis[i] = INF;

    mem[1] = INF;

    queue<int> bq;
    bq.push(1);

    while(!bq.empty())
    {
        int x = bq.front();
        int d = dis[x];
        bq.pop();

        for(edg &e : arr[x])
        {
            if(dis[e.y] < d + 1)
                continue;

            mem[e.y] = max(min(mem[x], e.w), mem[e.y]);

            if(dis[e.y] == INF)
            {
                dis[e.y] = dis[x] + 1;
                bq.push(e.y);
            }
        }
    }

    for(i = 1; i <= n; i++)
        if(mem[i] != INF)
            res[mem[i]]++;

    for(i = 1; i <= q; i++)
        res[i] += res[i - 1];

    for(i = 1; i <= q; i++)
        printf("%d\n", res[i]);
    return 0;
}

Compilation message (stderr)

2016_ho_t3.cpp: In function 'int main()':
2016_ho_t3.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
2016_ho_t3.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &ori[i][0], &ori[i][1]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2016_ho_t3.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &que[i]);
         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 39 / 39