oj.uz

Submission #137066

# Submission time Handle Problem Language Result Execution time Memory
137066 2019-07-27T03:39:50 Z arnold518 None (JOI16_ho_t3) C++14
0 / 100
 157 ms 13760 KB 
#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);
       }
    }
    sort(dist+1, dist+N+1);

    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});
    }

    /*
    for(i=1; i<=N; i++)
    {
        printf("%d : ", i);
        for(pii nxt : adj2[i]) printf("(%d %d) ", nxt.first, nxt.second);
        printf("\n");
    }
    */

    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

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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 157 ms 13760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4984 KB Output isn't correct
2 Halted 0 ms 0 KB -