제출 #96904

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96904		Kalam	Evacuation plan (IZhO18_plan)	C++11	100 / 100	1095 ms	67048 KiB

plan

// KALAM
# include<bits/stdc++.h>

using namespace std;

const int N = 500000 + 77;
int n , m , q , k , d[N] , Ev[N] , Eu[N] , Ew[N] , Qv[N] , Qu[N] , P[N] , A[N] , Par[N];
bool M[N];
vector < int > a[N];
set < int > S[N];
priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > Pq;
bool CMP(int x , int y){
   return Ew[x] > Ew[y];
}
int Find(int x){
   return Par[x] < 0 ? x : (Par[x] = Find(Par[x]));
}
inline void Merge(int v , int u , int w){
   v = Find(v);
   u = Find(u);
   if(v == u)
      return ;
   if(Par[v] > Par[u])
      swap(v , u);
   Par[v] += Par[u];
   Par[u] = v;
   for(int x : S[u]){
      auto it = S[v].lower_bound(x);
      if(it != S[v].end() && (*it) == x)
         A[x] = w , S[v].erase(it);
      else
         S[v].insert(x);
   }
   S[u].clear();
}
int main(){
   memset(Par , - 1 , sizeof(Par));
   memset(d , 63 , sizeof(d));
   scanf("%d %d" , & n , & m);
   for(int i = 1;i <= m;++ i) {
      scanf("%d %d %d" , Ev + i , Eu + i , Ew + i);
      a[Ev[i]].push_back(i);
      a[Eu[i]].push_back(i);
   }
   scanf("%d" , & k);
   while(k --){
      int x;
      scanf("%d" , & x);
      d[x] = 0;
      Pq.push(make_pair(d[x] , x));
   }
   while(! Pq.empty()){
      int v = Pq.top().second;
      Pq.pop();
      if(M[v])
         continue ;
      M[v] = 1;
      for(int id : a[v]){
         int u = Ev[id] ^ v ^ Eu[id] , w = Ew[id];
         if(d[u] <= d[v] + w)
            continue ;
         d[u] = d[v] + w;
         Pq.push(make_pair(d[u] , u));
      }
   }
   for(int i = 1;i <= m;++ i)
      P[i] = i , Ew[i] = min(d[Ev[i]] , d[Eu[i]]);
   sort(P + 1 , P + 1 + m , CMP);

   scanf("%d" , & q);
   for(int i = 1;i <= q;++ i){
      scanf("%d %d" , Qv + i , Qu + i);
      S[Qv[i]].insert(i);
      S[Qu[i]].insert(i);
   }
   for(int i = 1;i <= m;++ i){
      int id = P[i];
      Merge(Ev[id] , Eu[id] , Ew[id]);
   }
   for(int i = 1;i <= q;++ i)
      printf("%d\n" , A[i]);
   return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

plan.cpp: In function 'int main()':
plan.cpp:39:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d" , & n , & m);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~
plan.cpp:41:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d" , Ev + i , Eu + i , Ew + i);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:45:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d" , & k);
    ~~~~~^~~~~~~~~~~~
plan.cpp:48:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d" , & x);
       ~~~~~^~~~~~~~~~~~
plan.cpp:70:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d" , & q);
    ~~~~~^~~~~~~~~~~~
plan.cpp:72:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d" , Qv + i , Qu + i);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46