oj.uz

답안 #1096468

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1096468 2024-10-04T14:06:00 Z phong 철도 요금 (JOI16_ho_t3) C++17
0 / 100
 108 ms 43396 KB 
#include<bits/stdc++.h>
#define ll long long
const int nmax = 3e5 + 2, M = 3e5;
const ll oo = 1e9 + 5, base = 3001;
const int lg = 18,mod = 998244353;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, m, q;
vector<int> adj[nmax], one[nmax];
map<int, int>flag[nmax];
pii a[nmax]; int dp[nmax];

void Init(){
    for(int i = 1; i <= n; ++i) dp[i] = oo;
    dp[1] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, 1});
    while(q.size()){
        pii tmp = q.top();q.pop();
        int u = tmp.se;
        if(tmp.fi!= dp[u]) continue;
        for(auto v : adj[u]){
            if(dp[v] > dp[u] + 1){
                dp[v] = dp[u] + 1;
                q.push({dp[v], v});
            }
        }
    }
    for(int u = 1; u <= n; ++u){
        for(auto v : adj[u]){
            if(dp[v] == dp[u] + 1){
                one[u].push_back(v);
//                cout << u << ' ' << v << endl;
            }
        }
    }
}
void Init_2(){
    for(int i = 1; i <= n; ++i) dp[i] = oo;
    dp[1] = 0;
     priority_queue<pii, vector<pii>, greater<pii>> q;

    q.push({0, 1});
    while(q.size()){
        pii tmp = q.top();q.pop();
        int u = tmp.se;
        if(tmp.fi!= dp[u]) continue;
        for(auto v : one[u]){
            int cost =max(dp[u], flag[u][v]);
            if(dp[v] > cost){
                dp[v] = cost;
                q.push({dp[v], v});
            }
        }

    }
}
int b[nmax];

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> m >> q;
    for(int i = 1; i <= m; ++i){
        cin >> a[i].fi >> a[i].se;
        adj[a[i].fi].push_back(a[i].se);
        adj[a[i].se].push_back(a[i].fi);
    }
    Init();
    for(int e = 1,x; e<= q; ++e){
        cin >> x;
        flag[a[x].fi][a[x].se] = q - e + 1;
        flag[a[x].se][a[x].fi] = q - e + 1;
        b[e] = x;
    }

    Init_2();
    for(int i = 1; i <= q; ++i) dp[i] = q - dp[i] + 1;
//    debug(dp, n);
    sort(dp + 1, dp + 1 + n);
    for(int e = 1; e <= q; ++e){
        int it = upper_bound(dp + 1, dp + 1 + n, e) - dp - 1;
        cout << it <<endl;
    }
}
/*
số lượng dp
*/

Compilation message

2016_ho_t3.cpp:65:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   65 | main(){
      | ^~~~

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 28508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 28508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 108 ms 43396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 28508 KB Output isn't correct
2 Halted 0 ms 0 KB -