Submission #46844

#	Time	Username	Problem	Language	Result	Execution time	Memory
46844		Nnandi	Evacuation plan (IZhO18_plan)	C++14	0 / 100	357 ms	77176 KiB

plan

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

const int maxn=1000000;
const int maxkit=22;
int n, m, f, q;

struct El {
    int to, w;
    El() { }
    El(int erk, int suly) {
        to=erk;
        w=suly;
    }
    const bool operator< (El masik) const {
        return w>masik.w;
    }
};

vector<El> graf[maxn];
int d[maxn];
bool volte[maxn];

int hol[maxn];
vector<int> fa[maxn];

int hely[maxn];
vector<int> cron;


void init() {
    for(int i=0;i<n;i++) {
        hol[i]=i;
    }
    return;
}

int holvan(int u) {
    if(hol[u]!=u) {
        hol[u]=holvan(hol[u]);
    }
    return hol[u];
}

int t=0;

void bejar(int start, int apa) {
    cron.push_back(d[start]);
    hely[start]=t;
    t++;
    for(int s:fa[start]) {
        if(s!=apa) {
            bejar(s,start);
            cron.push_back(d[start]); t++;
        }
    }
    return;
}


int tab[maxn][maxkit];

void set_rmq() {
    for(int k=0;k<maxkit;k++) {
        for(int i=0;i<t;i++) {
            if(k==0) {
                tab[i][k]=cron[i];
            }
            else {
                int kezd=min(t-1,i+(1<<(k-1)));
                tab[i][k]=min(tab[i][k-1],tab[kezd][k-1]);
            }
        }
    }
    return;
}

int get_rmq(int from, int to) {
    if(to<from) {
        swap(from,to);
    }
    int l=to-from+1;
    int kl=log2(l);
    int kezd=min(t-1,to+1-(1<<kl));
    return min(tab[from][kl],tab[kezd][kl]);
}

vector<int> sol;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=0;i<m;i++) {
        int u, v, w;
        cin>>u>>v>>w;
        u--;
        v--;
        graf[u].push_back(El(v,w));
        graf[v].push_back(El(u,w));
    }
    priority_queue<El> kovi;
    cin>>f;
    for(int i=0;i<f;i++) {
        int s;
        cin>>s;
        s--;
        kovi.push(El(s,0));
    }
    while(!kovi.empty()) {
        El akt=kovi.top();
        kovi.pop();
        if(!volte[akt.to]) {
            volte[akt.to]=true;
            d[akt.to]=akt.w;
            for(El s:graf[akt.to]) {
                if(!volte[s.to]) {
                    s.w+=d[akt.to];
                    kovi.push(s);
                }
            }
        }
    }

    vector<pair<int,int> > tavol;
    for(int i=0;i<n;i++) {
        tavol.push_back(make_pair(d[i],i));
    }
    sort(tavol.begin(),tavol.end());
    reverse(tavol.begin(),tavol.end());
    init();
    for(auto ez:tavol) {
        int akt=ez.second;
        for(El s:graf[akt]) {
            if(holvan(akt)!=holvan(s.to) && d[s.to]>=d[akt]) {
                fa[akt].push_back(s.to);
                fa[s.to].push_back(akt);
                akt=holvan(akt);
                s.to=holvan(s.to);
                hol[s.to]=akt;
            }
        }
    }
    bejar(0,0);

    set_rmq();
    cin>>q;
    for(int i=0;i<q;i++) {
        int s, t;
        cin>>s>>t;
        s--; t--;
        sol.push_back(get_rmq(hely[s],hely[t]));
    }
    for(int d:sol) {
        cout<<d<<'\n';
    }
    return 0;
}

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