제출 #877954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
877954		oscar1f	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1913 ms	98708 KiB

plan

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int MAX_SOM=100*1000+5,MAX_REQ=100*1000+5,INFINI=(int)1000*1000*1000*1000*1000*1000;
int nbSom,nbAre,nbReq;
int debReq[MAX_REQ],finReq[MAX_REQ];
int debDicho[MAX_REQ],finDicho[MAX_REQ],quest[MAX_REQ];
bool ans[MAX_REQ];
vector<int> ajout[MAX_SOM];
unordered_map<int,int> corres;
int autreSens[MAX_SOM];
vector<pair<int,int>> adja[MAX_SOM];
int dist[MAX_SOM];
int pere[MAX_SOM];
vector<int> aRep[MAX_SOM];

int find(int pos) {
    if (pere[pos]!=pos) {
        pere[pos]=find(pere[pos]);
    }
    return pere[pos];
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbSom>>nbAre;
    int debAre,finAre,tailleAre;
    for (int i=0;i<nbAre;i++) {
        cin>>debAre>>finAre>>tailleAre;
        adja[debAre].push_back({finAre,tailleAre});
        adja[finAre].push_back({debAre,tailleAre});
    }
    for (int i=1;i<=nbSom;i++) {
        dist[i]=INFINI;
    }
    int nbDeb,posDeb;
    set<pair<int,int>> enCours;
    set<pair<int,int>>::iterator it;
    cin>>nbDeb;
    for (int i=0;i<nbDeb;i++) {
        cin>>posDeb;
        enCours.insert({0,posDeb});
    }
    int distCour,pos;
    while (!enCours.empty()) {
        it=enCours.begin();
        pos=(*it).second;
        distCour=(*it).first;
        enCours.erase(it);
        if (dist[pos]==INFINI) {
            dist[pos]=distCour;
            for (auto k:adja[pos]) {
                enCours.insert({distCour+k.second,k.first});
            }
        }
    }
    set<int> listeDist;
    for (int i=1;i<=nbSom;i++) {
        listeDist.insert(dist[i]);
    }
    int nbDist=0;
    for (int i:listeDist) {
        corres[i]=nbDist;
        autreSens[nbDist]=i;
        nbDist++;
    }
    for (int i=1;i<=nbSom;i++) {
        ajout[corres[dist[i]]].push_back(i);
        //cout<<i<<" : "<<dist[i]<<" "<<corres[dist[i]]<<endl;
    }

    cin>>nbReq;
    for (int i=0;i<nbReq;i++) {
        cin>>debReq[i]>>finReq[i];
        if (debReq[i]==finReq[i]) {
            debDicho[i]=corres[dist[debReq[i]]];
            finDicho[i]=corres[dist[debReq[i]]];
        }
        else {
            debDicho[i]=0;
            finDicho[i]=nbDist-1;
        }
    }
    for (int loop=0;loop<20;loop++) {
        for (int i=1;i<=nbSom;i++) {
            pere[i]=i;
        }
        for (int i=0;i<nbReq;i++) {
            if (debDicho[i]!=finDicho[i]) {
                quest[i]=(debDicho[i]+finDicho[i]+1)/2;
                aRep[quest[i]].push_back(i);
            }
        }
        for (int i=nbDist-1;i>=0;i--) {
            for (int j:ajout[i]) {
                //cout<<i<<" "<<j<<endl;
                for (auto k:adja[j]) {
                    if (dist[k.first]>=autreSens[i] and find(k.first)!=find(j)) {
                        //cout<<"+"<<i<<" "<<j<<" "<<k.first<<endl;
                        pere[find(k.first)]=find(j);                        
                    }
                }
            }
            for (int j:aRep[i]) {
                //cout<<j<<" : "<<find(debReq[j])<<" "<<find(finReq[j])<<endl;
                if (find(debReq[j])==find(finReq[j]) and dist[debReq[j]]>=autreSens[i] and dist[finReq[j]]>=autreSens[i]) {
                    ans[j]=true;
                }
                else {
                    ans[j]=false;
                }
            }
            aRep[i].clear();
        }
        for (int i=0;i<nbReq;i++) {
            if (debDicho[i]!=finDicho[i]) {
                //cout<<i<<" : "<<debDicho[i]<<" "<<finDicho[i]<<" "<<quest[i]<<" "<<ans[i]<<endl;
                if (ans[i]) {
                    debDicho[i]=quest[i];
                }
                else {
                    finDicho[i]=quest[i]-1;
                }
            }
        }
    }
    for (int i=0;i<nbReq;i++) {
        cout<<autreSens[debDicho[i]]<<"\n";
    }
    return 0;
}

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