Submission #1096467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096467		phong	철도 요금 (JOI16_ho_t3)	C++17	0 / 100	138 ms	47444 KiB

2016_ho_t3

#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 (stderr)

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

• Subtask 1: 0 / 12
• Subtask 2: 0 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 39