제출 #882817

#제출 시각아이디문제언어결과실행 시간메모리
882817ThylOneEvacuation plan (IZhO18_plan)C++14
41 / 100
2967 ms524288 KiB
//#################### //IZHO_2018_Plan //#################### #include<bits/stdc++.h> #define int long long using namespace std; const int INF=1e18; const int maxiNode = 2*100*1000; vector<pair<int,int>> links[maxiNode]; struct UnionFind{ vector<int> chef; vector<vector<int>> token_id; UnionFind(int _size){ chef.resize(_size); token_id.resize(_size); for(int i=0;i<_size;i++){ chef[i]=i; } } int find(int a){ if(chef[a]==a)return a; else return chef[a]=find(chef[a]); } vector<int> fusion(int a,int b){ int ra = find(a); int rb = find(b); if(ra!=rb){ chef[ra]=rb; vector<int> fusion_id = token_id[rb]; fusion_id.insert(fusion_id.end(),token_id[ra].begin(),token_id[ra].end()); token_id[ra].clear(); token_id[rb].clear(); sort(fusion_id.begin(),fusion_id.end()); vector<int> re; for(int i =0;i<fusion_id.size();i++){ if(i+1<fusion_id.size() && fusion_id[i]==fusion_id[i+1]){ re.push_back(fusion_id[i]); i++; }else{ token_id[rb].push_back(fusion_id[i]); } } return re; }else{ return {}; } } void debug_token_id(){ cout<<"××××××××××××××××××××××××××××××××××××"<<endl; for(int i=0;i<token_id.size();i++){ for(int v:token_id[i]){ cout<<v<<' '; } cout<<endl; } cout<<"××××××××××××××××××××××××××××××××××××"<<endl; } void addReq(int a,int b,int id){ token_id[a].push_back(id); token_id[b].push_back(id); } }; int minimal_distance[maxiNode]; bool comp(pair<int,int> &a,pair<int,int> &b){ int ra = min(minimal_distance[a.first],minimal_distance[a.second]); int rb = min(minimal_distance[b.first],minimal_distance[b.second]); return ra<rb; } signed main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m;cin>>n>>m; vector<pair<int,int>> edges; for(int i = 0;i<m;i++){ int a,b,w; cin>>a>>b>>w; a--;b--; links[a].push_back({b,w}); links[b].push_back({a,w}); edges.push_back({a,b}); } int k;cin>>k; vector<int> infected(k); for(int i=0;i<k;i++){ cin>>infected[i]; infected[i]--; } //Djikstra multi-source priority_queue<pair<int,int>> PQ; for(int i=0;i<k;i++){ PQ.push({-0,infected[i]}); } fill(minimal_distance,minimal_distance+n,-1); while(!PQ.empty()){ pair<int,int> act = PQ.top(); PQ.pop(); if(minimal_distance[act.second]!=-1){ continue; }else{ minimal_distance[act.second] = act.first * -1; for(auto p:links[act.second]){ PQ.push({(minimal_distance[act.second]+p.second)*-1,p.first}); } } } UnionFind UF(n); sort(edges.rbegin(),edges.rend(),comp); int q;cin>>q; int ans[q]; for(int i=0;i<q;i++){ int a,b;cin>>a>>b;a--;b--; UF.addReq(a,b,i); } for(int i=0;i<m;i++){ pair<int,int> &act = edges[i]; vector<int> re = UF.fusion(act.first,act.second); int W = min(minimal_distance[act.first],minimal_distance[act.second]); for(int i:re){ ans[i] = W; } } for(int i=0;i<q;i++){ cout<<ans[i]<<'\n'; } return 0; };

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

plan.cpp: In member function 'std::vector<long long int> UnionFind::fusion(long long int, long long int)':
plan.cpp:37:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for(int i =0;i<fusion_id.size();i++){
      |                          ~^~~~~~~~~~~~~~~~~
plan.cpp:38:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |                 if(i+1<fusion_id.size() && fusion_id[i]==fusion_id[i+1]){
      |                    ~~~^~~~~~~~~~~~~~~~~
plan.cpp: In member function 'void UnionFind::debug_token_id()':
plan.cpp:52:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int i=0;i<token_id.size();i++){
      |                     ~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...