oj.uz

답안 #545442

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
545442 2022-04-04T14:13:33 Z pokmui9909 철도 요금 (JOI16_ho_t3) C++17
12 / 100
 134 ms 22148 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define x first
#define y second
ll N, M, K;
pair<ll, ll> E[200005];
vector<pair<ll, ll>> G[200005];
ll dist[200005];
const ll INF = 1e18;
ll deg[200005];
ll chk[200005];

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    cin >> N >> M >> K;
    for(int i = 1; i <= M; i++){
        cin >> E[i].x >> E[i].y;
        G[E[i].x].push_back({E[i].y, i});
        G[E[i].y].push_back({E[i].x, i});
    }
    queue<ll> Q;
    fill(dist, dist + N + 1, INF);
    Q.push(1); dist[1] = 0;
    while(!Q.empty()){
        ll u = Q.front(); Q.pop();
        for(auto i : G[u]){
            if(dist[i.x] <= dist[u] + 1) continue;
            dist[i.x] = dist[u] + 1;
            Q.push(i.x);
        }
    }
    for(int i = 1; i <= M; i++){
        if(dist[E[i].x] == dist[E[i].y]) continue;
        if(dist[E[i].x] > dist[E[i].y]) swap(E[i].x, E[i].y);
        deg[E[i].y]++;
    }
    ll r = 0;
    while(K--){
        ll t; cin >> t;
        if(!chk[t] && dist[E[t].x] != dist[E[t].y]){
            Q.push(t); chk[t] = 1, deg[E[t].y]--;
            while(!Q.empty()){
                ll u = Q.front(); Q.pop();
                if(deg[E[u].y] == 0){
                    r++;
                    for(auto i : G[E[u].y]){
                        if(chk[i.y] || dist[E[i.y].x] == dist[E[i.y].y]) continue;
                        chk[i.y] = 1, deg[E[i.y].y]--;
                        Q.push(i.y);
                    }
                }
            }
        }
        cout << r << '\n';
    }
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5296 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5032 KB Output is correct
6 Correct 3 ms 5032 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 4 ms 4948 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5296 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5032 KB Output is correct
6 Correct 3 ms 5032 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 4 ms 4948 KB Output is correct
9 Correct 112 ms 20984 KB Output is correct
10 Correct 124 ms 20920 KB Output is correct
11 Correct 107 ms 20136 KB Output is correct
12 Correct 112 ms 20312 KB Output is correct
13 Correct 118 ms 20556 KB Output is correct
14 Correct 111 ms 20552 KB Output is correct
15 Incorrect 80 ms 16024 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 22148 KB Output is correct
2 Correct 129 ms 21940 KB Output is correct
3 Correct 74 ms 17336 KB Output is correct
4 Correct 107 ms 20780 KB Output is correct
5 Correct 103 ms 20616 KB Output is correct
6 Correct 114 ms 20664 KB Output is correct
7 Correct 58 ms 14160 KB Output is correct
8 Correct 56 ms 14056 KB Output is correct
9 Correct 35 ms 12748 KB Output is correct
10 Correct 32 ms 13000 KB Output is correct
11 Correct 126 ms 21168 KB Output is correct
12 Correct 116 ms 20668 KB Output is correct
13 Correct 109 ms 20324 KB Output is correct
14 Correct 126 ms 21804 KB Output is correct
15 Incorrect 134 ms 20424 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5296 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5032 KB Output is correct
6 Correct 3 ms 5032 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 4 ms 4948 KB Output is correct
9 Correct 112 ms 20984 KB Output is correct
10 Correct 124 ms 20920 KB Output is correct
11 Correct 107 ms 20136 KB Output is correct
12 Correct 112 ms 20312 KB Output is correct
13 Correct 118 ms 20556 KB Output is correct
14 Correct 111 ms 20552 KB Output is correct
15 Incorrect 80 ms 16024 KB Output isn't correct
16 Halted 0 ms 0 KB -