oj.uz

Submission #51169

# Submission time Handle Problem Language Result Execution time Memory
51169 2018-06-17T03:38:36 Z 노영훈(#1283, Diuven) None (JOI16_ho_t3) C++11
0 / 100
 2353 ms 13012 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 edge1 {
    int u, v, c, idx;
} E[2*MX];
vector<int> G[MX];

int init_dist[MX], ans;

bool do_upt(int r){
    int a=E[r].u, b=E[r].v;
    if(D[a].dist==D[b].dist) return false;
    if(D[a].dist>D[b].dist) swap(a,b);
    // D[b].dist == D[a].dist+1
    D[b].cnt-=D[a].cnt;
    return D[b].cnt==0;
}

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

void upt(){
    // dijk?
    for(int i=1; i<=n; i++)
        D[i]={inf, 0, 0};
    D[1]={0,1,0};

    priority_queue<edge2> Q;
    Q.push({1,0});
    while(!Q.empty()){
        int v=Q.top().to, c=Q.top().co; Q.pop();
        if(D[v].dist!=c) continue;
        for(int e:G[v]){
            int x=E[e].u, y=E[e].v, z=(x==v ? y : x);
            int dvz=c+E[e].c, 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, D[z].dist});
            }
        }
    }
    ans=0;
    for(int i=1; i<=n; i++)
        if(init_dist[i]!=D[i].dist) ans++;
}

void init(){
    upt();
    for(int i=1; i<=n; i++)
        init_dist[i]=D[i].dist;
    ans=0;
}

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);
    }
    init();
    for(int i=1, r; i<=q; i++){
        cin>>r;
        E[r].c=2;
        if(do_upt(r)) upt();
        cout<<ans<<'\n';
    }
    return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2824 KB Output is correct
3 Correct 5 ms 3112 KB Output is correct
4 Correct 4 ms 3112 KB Output is correct
5 Correct 4 ms 3112 KB Output is correct
6 Correct 4 ms 3112 KB Output is correct
7 Correct 4 ms 3112 KB Output is correct
8 Incorrect 5 ms 3112 KB Output isn't correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2824 KB Output is correct
3 Correct 5 ms 3112 KB Output is correct
4 Correct 4 ms 3112 KB Output is correct
5 Correct 4 ms 3112 KB Output is correct
6 Correct 4 ms 3112 KB Output is correct
7 Correct 4 ms 3112 KB Output is correct
8 Incorrect 5 ms 3112 KB Output isn't correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2229 ms 13012 KB Output is correct
2 Correct 2271 ms 13012 KB Output is correct
3 Correct 1564 ms 13012 KB Output is correct
4 Correct 2353 ms 13012 KB Output is correct
5 Correct 1318 ms 13012 KB Output is correct
6 Correct 1482 ms 13012 KB Output is correct
7 Correct 893 ms 13012 KB Output is correct
8 Correct 960 ms 13012 KB Output is correct
9 Correct 804 ms 13012 KB Output is correct
10 Correct 815 ms 13012 KB Output is correct
11 Incorrect 2192 ms 13012 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2824 KB Output is correct
3 Correct 5 ms 3112 KB Output is correct
4 Correct 4 ms 3112 KB Output is correct
5 Correct 4 ms 3112 KB Output is correct
6 Correct 4 ms 3112 KB Output is correct
7 Correct 4 ms 3112 KB Output is correct
8 Incorrect 5 ms 3112 KB Output isn't correct