oj.uz

Submission #51166

# Submission time Handle Problem Language Result Execution time Memory
51166 2018-06-17T02:56:25 Z 노영훈(#1283, Diuven) None (JOI16_ho_t3) C++11
26 / 100
 2500 ms 12228 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int MX=100010, inf=2e9;

int n, m, q;
int Q[MX];
struct node {
    int dist, cnt, sub;
} D[MX];
struct edge {
    int u, v, c, idx;
} E[2*MX];
vector<int> G[MX];

void init(){
    for(int i=1; i<=n; i++)
        D[i]={inf, 0, 0};
    D[1]={0,1,0};
    queue<int> Q; Q.push(1);
    while(!Q.empty()){
        int v=Q.front(); Q.pop();
        for(int e:G[v]){
            int x=E[e].u, y=E[e].v, z=(x==v ? y : x);
            int dvz=D[v].dist+1, dz=D[z].dist;
            if(dvz>dz) continue;
            if(dvz==dz) D[z].cnt+=D[v].cnt;
            if(dvz<dz){
                D[z]={dvz, D[v].cnt, 0};
                Q.push(z);
            }
        }
    }
}

int dist[MX];

struct edge2 {
    int to, cost;
    bool operator < (const edge2& e) const {
        return cost > e.cost;
    }
};

void prec(){
    fill(dist, dist+n+1, inf);
    dist[1]=0;
    priority_queue<edge2> Q;
    Q.push({1,0});
    while(!Q.empty()){
        int v=Q.top().to, co=Q.top().cost; Q.pop();
        if(dist[v]!=co) continue;
        for(int e:G[v]){
            int a=E[e].u, b=E[e].v, x=(a==v ? b : a);
            if(dist[x]<=dist[v]+E[e].c) continue;
            dist[x]=dist[v]+E[e].c;
            Q.push({x, dist[x]});
        }
    }    
}

int upt(int e){
    E[e].c=2;

    int W[MX]={};
    fill(W, W+n+1, inf);
    W[1]=0;
    priority_queue<edge2> Q;
    Q.push({1,0});
    while(!Q.empty()){
        int v=Q.top().to, co=Q.top().cost; Q.pop();
        if(W[v]!=co) continue;
        for(int e:G[v]){
            int a=E[e].u, b=E[e].v, x=(a==v ? b : a);
            if(W[x]<=W[v]+E[e].c) continue;
            W[x]=W[v]+E[e].c;
            Q.push({x, W[x]});
        }
    }

    int res=0;

    for(int i=1; i<=n; i++)
        if(W[i]!=dist[i]){
            res++;
        }
    return res;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>q;
    for(int i=1, u, v; i<=m; i++){
        cin>>u>>v;
        E[i]={u,v,1,i};
        G[u].push_back(i);
        G[v].push_back(i);
    }
    prec();
    for(int i=1, r; i<=q; i++){
        cin>>r;
        cout<<upt(r)<<'\n';
    }
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 5 ms 3304 KB Output is correct
3 Correct 7 ms 3304 KB Output is correct
4 Correct 5 ms 3304 KB Output is correct
5 Correct 5 ms 3304 KB Output is correct
6 Correct 5 ms 3304 KB Output is correct
7 Correct 5 ms 3304 KB Output is correct
8 Correct 5 ms 3304 KB Output is correct
9 Correct 1536 ms 12228 KB Output is correct
10 Correct 1624 ms 12228 KB Output is correct
11 Correct 895 ms 12228 KB Output is correct
12 Correct 809 ms 12228 KB Output is correct
13 Correct 618 ms 12228 KB Output is correct
14 Correct 542 ms 12228 KB Output is correct
15 Correct 439 ms 12228 KB Output is correct
16 Correct 457 ms 12228 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2563 ms 12228 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 5 ms 3304 KB Output is correct
3 Correct 7 ms 3304 KB Output is correct
4 Correct 5 ms 3304 KB Output is correct
5 Correct 5 ms 3304 KB Output is correct
6 Correct 5 ms 3304 KB Output is correct
7 Correct 5 ms 3304 KB Output is correct
8 Correct 5 ms 3304 KB Output is correct
9 Correct 1536 ms 12228 KB Output is correct
10 Correct 1624 ms 12228 KB Output is correct
11 Correct 895 ms 12228 KB Output is correct
12 Correct 809 ms 12228 KB Output is correct
13 Correct 618 ms 12228 KB Output is correct
14 Correct 542 ms 12228 KB Output is correct
15 Correct 439 ms 12228 KB Output is correct
16 Correct 457 ms 12228 KB Output is correct
17 Execution timed out 2563 ms 12228 KB Time limit exceeded
18 Halted 0 ms 0 KB -