Submission #1301416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301416		StefanSebez	철도 요금 (JOI16_ho_t3)	C++20	100 / 100	105 ms	18768 KiB

2016_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=1e5+50,inf=1e9;
vector<int>E[N],E1[N];
bool active[N];
int num=1;
void DFS(int u){
    if(!active[u])num++;active[u]=true;
    for(auto i:E1[u]) DFS(i);
    E1[u].clear();
}
int main(){
    int n,m,q;scanf("%i%i%i",&n,&m,&q);
    pair<int,int>edges[m+10];
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%i%i",&u,&v);
        E[u].pb(v),E[v].pb(u);
        edges[i]={u,v};
    }
    vector<int>ind;bool ubacen[m+10]={0};
    for(int i=0;i<q;i++){
        int j;scanf("%i",&j);
        ind.pb(j);ubacen[j]=true;
    }
    for(int i=1;i<=m;i++)if(!ubacen[i])ind.pb(i);
    reverse(ind.begin(),ind.end());
    int dist[n+10];for(int i=1;i<=n;i++)dist[i]=inf;
    queue<int>kju;dist[1]=0;kju.push(1);
    while(!kju.empty()){
        int u=kju.front();kju.pop();
        for(auto i:E[u])if(dist[i]>dist[u]+1)dist[i]=dist[u]+1,kju.push(i);
    }
    vector<int>res;
    active[1]=true;
    for(auto I:ind){
        res.pb(n-num);
        auto [u,v]=edges[I];
        if(dist[u]>dist[v])swap(u,v);
        if(dist[v]==dist[u]+1){
            E1[u].pb(v);
            if(active[u]&&!active[v]) DFS(u);
        }
    }
    reverse(res.begin(),res.end());
    res.resize(q);
    for(auto i:res) printf("%i\n",i);
    return 0;
}

Compilation message (stderr)

2016_ho_t3.cpp: In function 'int main()':
2016_ho_t3.cpp:19:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     int n,m,q;scanf("%i%i%i",&n,&m,&q);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~
2016_ho_t3.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%i%i",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~
2016_ho_t3.cpp:29:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         int j;scanf("%i",&j);
      |               ~~~~~^~~~~~~~~

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