Submission #117159

#	Time	Username	Problem	Language	Result	Execution time	Memory
117159		onjo0127	철도 요금 (JOI16_ho_t3)	C++11	100 / 100	178 ms	17536 KiB

2016_ho_t3

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

struct edge {
    int u, v, t;
} E[200009];

vector<pii> adj[100009];
int dep[100009], D[100009], dif[200009];

int main() {
    int N, M, Q; scanf("%d%d%d",&N,&M,&Q);
    for(int i=1; i<=M; i++) {
        scanf("%d%d", &E[i].u, &E[i].v);
        E[i].t = Q+1;
    }
    for(int i=1; i<=Q; i++) {
        int foo; scanf("%d",&foo);
        E[foo].t = i;
    }
    for(int i=1; i<=M; i++) {
        int x = E[i].u, y = E[i].v, c = E[i].t;
        adj[x].push_back({y, c});
        adj[y].push_back({x, c});
    }
    queue<int> que; que.push(1); dep[1] = 1; D[1] = Q+1;
    int d = 1;
    while(que.size()) {
        int sz = que.size();
        while(sz--) {
            int now = que.front(); que.pop();
            ++dif[D[now]];
            for(auto& it: adj[now]) {
                if(!dep[it.first]) {
                    dep[it.first] = d + 1;
                    D[it.first] = min(D[now], it.second);
                    que.push(it.first);
                }
                else if(dep[it.first] == d + 1) {
                    D[it.first] = max(D[it.first], min(D[now], it.second));
                }
            }
        }
        ++d;
    }
    for(int i=1, s=0; i<=Q; i++) {
        s += dif[i];
        printf("%d\n",s);
    }
    return 0;
}

Compilation message (stderr)

2016_ho_t3.cpp: In function 'int main()':
2016_ho_t3.cpp:13:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int N, M, Q; scanf("%d%d%d",&N,&M,&Q);
                  ~~~~~^~~~~~~~~~~~~~~~~~~
2016_ho_t3.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &E[i].u, &E[i].v);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
2016_ho_t3.cpp:19:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int foo; scanf("%d",&foo);
                  ~~~~~^~~~~~~~~~~

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