Submission #89896

#	Time	Username	Problem	Language	Result	Execution time	Memory
89896		Abelyan	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1217 ms	96316 KiB

plan

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

const int N=500005;
const int LG=log2(N)+3;

#define fr first
#define sc second

int l;
int anc[N][LG];
int in[N],out[N],timer;

void dfs(int v,vector<int>* g,int par=0){
    //cout<<v<<endl;
    in[v]=timer++;
    anc[v][0]=par;
    for (int i=1;i<=l;i++){
        anc[v][i]=anc[anc[v][i-1]][i-1];
    }
    for (auto to:g[v]){
        if (to==par)continue;
        dfs(to,g,v);
    }
    out[v]=timer++;
}

bool is_anc(int a,int b){
    if (b==0 || a==b)return true;
    if (in[a]>in[b] && in[a]<out[b])return true;
    return false;
}

int lca(int a,int b){
    if (is_anc(a,b)) return b;
    if (is_anc(b,a)) return a;
    for (int i=l;i>=0;i--)
        if (!is_anc(b,anc[a][i]))
            a=anc[a][i];
    return anc[a][0];
}
void prec(int n,int root,vector<int>* g){
    l=0;
    while ((1<<l)<=n)l++;
    dfs(root,g);
}

vector<pair<int,int> > g[N];
vector<int> gr[N];
int dp[N],inComp[N],node[N],val[N];
bool col[N];
vector<int> comp[N];

int main(){
    ios_base::sync_with_stdio(false);
    //freopen("input.txt","r",stdin);
    int n,m;
    cin>>n>>m;
    for (int i=0;i<m;i++){
        int a,b,l;
        cin>>a>>b>>l;
        g[a].push_back({b,l});
        g[b].push_back({a,l});
    }
    for (int i=1;i<=n;i++){
        dp[i]=INT_MAX;
    }
    priority_queue<pair<int,int> > pq;
    int blackNum;
    cin>>blackNum;
    for (int i=0;i<blackNum;i++){
        int k;
        cin>>k;
        dp[k]=0;
        pq.push({0,k});
    }
    while (!pq.empty()){
        int cur;
        do{
            cur=pq.top().sc;
            pq.pop();
        }while(col[cur] && !pq.empty());
        if (col[cur])break;
        col[cur]=true;
        for (auto to:g[cur]){
            if (dp[cur]+to.sc<dp[to.fr]){
                dp[to.fr]=dp[cur]+to.sc;
                pq.push({-dp[to.fr],to.fr});
            }
        }
    }
    vector<pair<int,pair<int,int> > >v;
    for (int i=1;i<=n;i++){
        //cout<<dp[i]<<" ";
        inComp[i]=i;
        node[i]=i;
        comp[i].push_back(i);
        for (auto to:g[i]){
            v.push_back({-min(dp[to.fr],dp[i]),{i,to.fr}});
        }
    }
    //cout<<endl;
    sort(v.begin(),v.end());
    int cnt=n+1;
    for (int i=0;i<v.size();i++){
        int a=v[i].sc.fr,b=v[i].sc.sc,len=-v[i].fr;
        if (inComp[a]==inComp[b])continue;
        //cout<<a<<" "<<b<<" ";
        a=inComp[a];
        b=inComp[b];
        //cout<<a<<" "<<b<<endl;
        gr[cnt].push_back(node[a]);
        gr[cnt].push_back(node[b]);
        //cout<<cnt<<" "<<node[a]<<" "<<node[b]<<endl;
        if (comp[a].size()<comp[b].size())swap(a,b);
        for (auto tv:comp[b]){
            inComp[tv]=a;
            comp[a].push_back(tv);
        }
        val[cnt]=len;
        node[a]=cnt++;
    }
    prec(cnt-1,cnt-1,gr);
    int q;
    cin>>q;
    for (int i=0;i<q;i++){
        int a,b;
        cin>>a>>b;
        cout<<val[lca(a,b)]<<endl;
    }
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:105:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v.size();i++){
                  ~^~~~~~~~~

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