Submission #882818

#	Time	Username	Problem	Language	Result	Execution time	Memory
882818		ThylOne	Evacuation plan (IZhO18_plan)	C++14	41 / 100	4037 ms	59428 KiB

plan

        //####################
        //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){
            if(token_id[rb].size()<token_id[ra].size())swap(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;
};

Compilation message (stderr)

plan.cpp: In member function 'std::vector<long long int> UnionFind::fusion(long long int, long long int)':
plan.cpp:38: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]
   38 |             for(int i =0;i<fusion_id.size();i++){
      |                          ~^~~~~~~~~~~~~~~~~
plan.cpp:39: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]
   39 |                 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:53: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]
   53 |         for(int i=0;i<token_id.size();i++){
      |                     ~^~~~~~~~~~~~~~~~

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