Submission #93562

#	Time	Username	Problem	Language	Result	Execution time	Memory
93562		muradeyn	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1078 ms	79836 KiB

plan

/* Murad Eynizade */
 
#include <bits/stdc++.h>
#define int long long
#define FAST_READ ios_base::sync_with_stdio(0);cin.tie(0);
#define SIZE 100001
#define INF INT_MAX
#define F first
#define S second
#define in(a) scanf("%d",&a);
#define outn(a) printf("%d\n",&a);
#define outs(a) printf("%d ",&a);
#define LOG 18
 
using namespace std;
 
int n , m , w , d[SIZE] , sze[SIZE] , par[SIZE] , lvl[SIZE] , p[SIZE][LOG] , q , ans , val[SIZE][LOG];
 
vector< pair<int,int> >v[SIZE];
 
vector< pair< int , pair<int,int> > >edges;
 
priority_queue< pair<int,int> >pq;
 
void init() {
    for (int i = 1;i<SIZE;i++) {
        d[i] = INF;
        sze[i] = 1;
        par[i] = i;
    }
}
 
void dijkstra() {
    while (!pq.empty()) {
        int u = pq.top().S, dd = pq.top().F; pq.pop();
        if (dd != -d[u]) continue;
        for (auto i : v[u]) {
            int to = i.first , we = i.second;
            if (d[to] > d[u] + we) {
                //cout<<to<<" "<<d[to]<<endl;
                //cout<<u<<" "<<d[u]<<endl;
                //cout<<we<<endl;
                //char aa;
                //cin>>aa;
                d[to] = d[u] + we;
                pq.push({-d[to] , to});
            }
        }
    }
}
 
int find_root(int a) {
    if (a == par[a]) return a;
    return par[a] = find_root(par[a]);
}
 
void dfs(int s,int pa,int l) {
    lvl[s] = l;
    p[s][0] = pa;
    val[s][0] = d[s];
    for (auto i : v[s]) {
        int to = i.F;
        if (to == pa)continue;
        dfs(to,s,l + 1);
    }
}
 
int lg(int x) {
    int ret = 0;
    while (x > 1) {
        ret++;
        x /= 2;
    }
    return ret;
}
 
int lca(int x,int y) {
    if (lvl[x] < lvl[y])swap(x,y);
    while (lvl[x] != lvl[y]) {
        int dist = lvl[x] - lvl[y];
        int lg2 = lg(dist);
        ans = min(ans , val[x][lg2]);
        x = p[x][lg2];
        ans = min(ans,d[x]);
    }
    if (x == y)return ans;
    for (int i = LOG - 1;i >= 0;i--) {
        if (p[x][i] != p[y][i]) {
            ans = min(ans , val[x][i]);
            x = p[x][i];
            ans = min(ans,d[x]);
            ans = min(ans , val[y][i]);
            y = p[y][i];
            ans = min(ans,d[y]);
        }
    }
    return min(ans,val[p[x][0]][0]);
}
 
int x,y;
 
main()
{
    FAST_READ;
    init();
    cin>>n>>m;
    while (m--) {
        cin>>x>>y>>w;
        v[x].push_back({y,w});
        v[y].push_back({x,w});
        edges.push_back({-1,{x,y}});
    }
    cin>>m;
    while (m--) {
        cin>>x;
        d[x] = 0;
        pq.push({0,x});
    }
    dijkstra();
    for (int i = 0;i<edges.size();i++) {
        edges[i].F = -min(d[edges[i].S.F] , d[edges[i].S.S]);
    }
    sort(edges.begin(),edges.end());
    int co = 0;
    //for (int i = 1;i<=n;i++)cout<<i<<" "<<d[i]<<endl;
    for (int i = 1;i<=n;i++) v[i].clear();
    for (auto i : edges) {
        int roota = find_root(i.S.F);
        int rootb = find_root(i.S.S);
        if (roota == rootb) continue;
        //cout<<i.S.F<<" "<<i.S.S<<endl;
        v[i.S.F].push_back({i.S.S,-1});
        v[i.S.S].push_back({i.S.F,-1});
        if (sze[i.S.F] < sze[i.S.S]) {
            sze[i.S.S] += sze[i.S.F];
            par[roota] = rootb;
        }
        else {
            sze[i.S.F] += sze[i.S.S];
            par[rootb] = roota;
        }
        co++;
        if (co == n - 1)break;
    }
    memset(p,-1,sizeof(p));
    dfs(1,-1,1);
    for (int j = 1;j < LOG;j++) {
        for (int i = 1;i<=n;i++) {
            if (p[i][j - 1] == -1)p[i][j] = -1;
            else p[i][j] = p[p[i][j - 1]][j - 1];
        }
    }
    for (int j = 1;j < LOG;j++) {
        for (int i = 1;i<=n;i++) {
            if (p[i][j - 1] == -1)val[i][j] = val[i][j - 1];
            else val[i][j] = min(val[i][j - 1],val[p[i][j - 1]][j - 1]);
        }
    }
    cin>>q;
    while (q--) {
        cin>>x>>y;
        ans = min(d[x],d[y]);
        cout<<lca(x,y)<<endl;
    }
    return 0;
}

Compilation message (stderr)

plan.cpp:102:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
plan.cpp: In function 'int main()':
plan.cpp:120:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0;i<edges.size();i++) {
                    ~^~~~~~~~~~~~~

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