oj.uz

Submission #503644

# Submission time Handle Problem Language Result Execution time Memory
503644 2022-01-08T14:04:37 Z jk410 None (JOI16_ho_t3) C++17
61 / 100
 2500 ms 15856 KB 
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct nosun{
    int u,v;
};
struct edge{
    int v,cost;
    bool operator<(const edge &tmp)const{
        return cost>tmp.cost;
    }
};
int N,M,Q;
nosun Nosun[200001];
int R[200001];
bool Used[200001];
vector<int> Edge[100001];
int D[100001];
int Dist[100001];
priority_queue<edge> PQ;
int Ans[200001];
void dijkstra(int t){
    while (!PQ.empty()){
        edge tmp=PQ.top();
        PQ.pop();
        if (Dist[tmp.v]<tmp.cost)
            continue;
        for (int i:Edge[tmp.v]){
            if (Dist[i]>tmp.cost+1){
                D[i]=t;
                Dist[i]=tmp.cost+1;
                PQ.push({i,Dist[i]});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>M>>Q;
    for (int i=1; i<=N; i++){
        D[i]=Q+1;
        Dist[i]=INF;
    }
    for (int i=1; i<=M; i++)
        cin>>Nosun[i].u>>Nosun[i].v;
    for (int i=1; i<=Q; i++){
        cin>>R[i];
        Used[R[i]]=true;
    }
    for (int i =1; i<=M; i++){
        if (Used[i])
            continue;
        Edge[Nosun[i].u].push_back(Nosun[i].v);
        Edge[Nosun[i].v].push_back(Nosun[i].u);
    }
    Dist[1]=0;
    PQ.push({1,0});
    dijkstra(Q+1);
    for (int i=Q; i; i--){
        Edge[Nosun[R[i]].u].push_back(Nosun[R[i]].v);
        Edge[Nosun[R[i]].v].push_back(Nosun[R[i]].u);
        int v;
        if (Dist[Nosun[R[i]].u]>Dist[Nosun[R[i]].v])
            v=Nosun[R[i]].v;
        else
            v=Nosun[R[i]].u;
        PQ.push({v,Dist[v]});
        dijkstra(i);
    }
    for (int i=1; i<=N; i++){
        if (D[i]==Q+1)
            continue;
        Ans[D[i]]++;
    }
    for (int i=1; i<=Q; i++){
        Ans[i]+=Ans[i-1];
        cout<<Ans[i]<<"\n";
    }
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 1 ms 2636 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 1 ms 2636 KB Output is correct
9 Correct 74 ms 12188 KB Output is correct
10 Correct 120 ms 12220 KB Output is correct
11 Correct 72 ms 11468 KB Output is correct
12 Correct 63 ms 11512 KB Output is correct
13 Correct 68 ms 11512 KB Output is correct
14 Correct 73 ms 11392 KB Output is correct
15 Correct 39 ms 8824 KB Output is correct
16 Correct 32 ms 8516 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 12296 KB Output is correct
2 Correct 115 ms 12240 KB Output is correct
3 Correct 65 ms 11320 KB Output is correct
4 Correct 60 ms 11512 KB Output is correct
5 Correct 61 ms 11432 KB Output is correct
6 Correct 94 ms 11400 KB Output is correct
7 Correct 49 ms 8644 KB Output is correct
8 Correct 33 ms 8560 KB Output is correct
9 Correct 28 ms 8572 KB Output is correct
10 Correct 39 ms 8856 KB Output is correct
11 Correct 86 ms 12728 KB Output is correct
12 Correct 76 ms 12076 KB Output is correct
13 Correct 74 ms 11872 KB Output is correct
14 Correct 91 ms 12500 KB Output is correct
15 Correct 109 ms 12160 KB Output is correct
16 Correct 80 ms 11928 KB Output is correct
17 Correct 82 ms 12688 KB Output is correct
18 Correct 64 ms 10552 KB Output is correct
19 Correct 122 ms 15688 KB Output is correct
20 Correct 79 ms 12636 KB Output is correct
21 Correct 46 ms 9484 KB Output is correct
22 Correct 49 ms 9476 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 1 ms 2636 KB Output is correct
9 Correct 74 ms 12188 KB Output is correct
10 Correct 120 ms 12220 KB Output is correct
11 Correct 72 ms 11468 KB Output is correct
12 Correct 63 ms 11512 KB Output is correct
13 Correct 68 ms 11512 KB Output is correct
14 Correct 73 ms 11392 KB Output is correct
15 Correct 39 ms 8824 KB Output is correct
16 Correct 32 ms 8516 KB Output is correct
17 Correct 73 ms 12296 KB Output is correct
18 Correct 115 ms 12240 KB Output is correct
19 Correct 65 ms 11320 KB Output is correct
20 Correct 60 ms 11512 KB Output is correct
21 Correct 61 ms 11432 KB Output is correct
22 Correct 94 ms 11400 KB Output is correct
23 Correct 49 ms 8644 KB Output is correct
24 Correct 33 ms 8560 KB Output is correct
25 Correct 28 ms 8572 KB Output is correct
26 Correct 39 ms 8856 KB Output is correct
27 Correct 86 ms 12728 KB Output is correct
28 Correct 76 ms 12076 KB Output is correct
29 Correct 74 ms 11872 KB Output is correct
30 Correct 91 ms 12500 KB Output is correct
31 Correct 109 ms 12160 KB Output is correct
32 Correct 80 ms 11928 KB Output is correct
33 Correct 82 ms 12688 KB Output is correct
34 Correct 64 ms 10552 KB Output is correct
35 Correct 122 ms 15688 KB Output is correct
36 Correct 79 ms 12636 KB Output is correct
37 Correct 46 ms 9484 KB Output is correct
38 Correct 49 ms 9476 KB Output is correct
39 Correct 136 ms 15840 KB Output is correct
40 Correct 212 ms 15856 KB Output is correct
41 Execution timed out 2561 ms 11212 KB Time limit exceeded
42 Halted 0 ms 0 KB -