Submission #137079

#	Time	Username	Problem	Language	Result	Execution time	Memory
137079		arnold518	철도 요금 (JOI16_ho_t3)	C++14	100 / 100	269 ms	21496 KiB

2016_ho_t3

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int MAXM = 2e5;
const int INF = 987654321;

struct Edge { int u, v; };

int N, M, Q, query[MAXM+10];
vector<int> adj[MAXN+10];
vector<pii> adj2[MAXN+10];
Edge edge[MAXM+10];

pii dist[MAXN+10];
int dp[MAXN+10], ans[MAXM+10];

int main()
{
    int i, j;
    scanf("%d%d%d", &N, &M, &Q);
    for(i=1; i<=M; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
        edge[i]={u, v};
    }
    for(i=1; i<=Q; i++)
    {
        int t;
        scanf("%d", &t);
        query[t]=i;
    }

    for(i=1; i<=N; i++) dist[i]={-1, i};
    queue<int> BQ; dist[1].first=0; BQ.push(1);
    while(!BQ.empty())
    {
       int now=BQ.front();
       BQ.pop();

       for(int nxt : adj[now])
       {
           if(dist[nxt].first!=-1) continue;
           dist[nxt].first=dist[now].first+1;
           BQ.push(nxt);
       }
    }

    for(i=1; i<=M; i++)
    {
        Edge &now=edge[i];
        int t=INF;
        if(query[i]!=0) t=query[i];
        if(dist[now.u].first+1==dist[now.v].first) adj2[now.v].push_back({now.u, t});
        else if(dist[now.v].first+1==dist[now.u].first) adj2[now.u].push_back({now.v, t});
    }
    sort(dist+1, dist+N+1);

    dp[1]=INF;
    for(i=2; i<=N; i++)
    {
        int now=dist[i].second;
        for(pii nxt : adj2[now]) dp[now]=max(dp[now], min(dp[nxt.first], nxt.second));
        if(dp[now]!=INF) ans[dp[now]]++;
        //printf("%d %d\n", now, dp[now]);
    }
    for(i=1; i<=Q; i++) ans[i]+=ans[i-1];
    for(i=1; i<=Q; i++) printf("%d\n", ans[i]);
}

Compilation message (stderr)

2016_ho_t3.cpp: In function 'int main()':
2016_ho_t3.cpp:24:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
2016_ho_t3.cpp:25: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:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~
2016_ho_t3.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &t);
         ~~~~~^~~~~~~~~~

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