oj.uz

Submission #137065

# Submission time Handle Problem Language Result Execution time Memory
137065 2019-07-27T03:37:22 Z arnold518 None (JOI16_ho_t3) C++14
0 / 100
 132 ms 21624 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[MAXN+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});
    }

    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]]++;
    }
    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 5112 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 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 132 ms 21624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

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