oj.uz

Submission #46844

# Submission time Handle Problem Language Result Execution time Memory
46844 2018-04-23T19:07:23 Z Nnandi Evacuation plan (IZhO18_plan) C++14
0 / 100
 357 ms 77176 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 47380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 47380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47272 KB Output is correct
2 Incorrect 44 ms 47324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 357 ms 77176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 47380 KB Output isn't correct
2 Halted 0 ms 0 KB -