Submission #93016

#	Time	Username	Problem	Language	Result	Execution time	Memory
93016		muradeyn	Evacuation plan (IZhO18_plan)	C++14	23 / 100	992 ms	60800 KiB

plan

/* Murad Eynizade */

#include <bits/stdc++.h>
#define intt long long
#define FAST_READ ios_base::sync_with_stdio(0);cin.tie(0);
#define SIZE 200001
#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 19

using namespace std;

int n , m , k , x , y , w , d[SIZE] , sze[SIZE] , p[SIZE] , edges , lvl[SIZE] , par[SIZE][LOG] , val[SIZE][LOG] , q , lgg[SIZE] , f[SIZE] , table[SIZE][LOG];

vector< pair<int,int> >v[SIZE];

vector<int>euler;

priority_queue< pair<int,int> >pq;

void dijkstra() {
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        for (auto i : v[u]) {
            int to = i.F , we = i.S;
            if (d[to] > d[u] + we) {
                d[to] = d[u] + we;
                pq.push({-d[to] , to});
            }
        }
    }
}

int find_root(int a) {
    if (a == p[a])return a;
    return p[a] = find_root(p[a]);
}

void init() {
    for (int i = 1;i<=n;i++) {
        d[i] = INF;
        sze[i] = 1;
        p[i] = i;
    }
}

vector< pair< int , pair<int,int> > >st;

void dfs(int s,int p,int l) {
    lvl[s] = l;
    par[s][0] = p;
    val[s][0] = d[s];
    f[s] = euler.size() + 1;
    euler.push_back(s);
    for (auto i : v[s]) {
        int to = i.F;
        if (p == to)continue;
        dfs(to , s , l + 1);
        euler.push_back(s);
    }
}

int lg2(int x) {
    int ret = 0;
    while (x > 1) {
        ret++;
        x /= 2;
    }
    return ret;
}

int lca(int x,int y,int l) {
    int ans = min(d[x],d[y]);
    while (lvl[x] != l) {
        int dist = lvl[x] - l;
        int lg = lg2(dist);
        ans = min(ans,val[x][lg]);
        x = par[x][lg];
    }
    while (lvl[y] != l) {
        int dist = lvl[y] - l;
        int lg = lg2(dist);
        ans = min(ans,val[y][lg]);
        y = par[y][lg];
    }
    return ans;
}

int main()
{
    FAST_READ;
    lgg[1] = 0;
    for (int i = 2;i<SIZE;i++)lgg[i] = lgg[i / 2] + 1;
    cin>>n>>m;
    init();
    for (int i = 1;i<=m;i++) {
        cin>>x>>y>>w;
        v[x].push_back({y,w});
        v[y].push_back({x,w});
        st.push_back({-w , {x , y}});
    }
    cin>>k;
    while (k--) {
        cin>>x;
        pq.push({0,x});
        d[x] = 0;
    }
    dijkstra();
    for (int i = 0;i<st.size();i++) {
        st[i].F = -min(d[st[i].S.F] , d[st[i].S.S]);
        //cout<<i.S.F<<" "<<i.S.S<<endl;
        //cout<<d[i.S.F]<<" "<<d[i.S.S]<<endl;
        //cout<<i.F<<endl;
    }
    sort(st.begin(),st.end());
    for (int i = 1;i<=n;i++)v[i].clear();
    for (auto i : st) {
        int roota = find_root(i.S.F);
        int rootb = find_root(i.S.S);
        if (roota == rootb)continue;
        v[i.S.F].push_back({i.S.S , i.F});
        v[i.S.S].push_back({i.S.F , i.F});
        if (sze[roota] < sze[rootb]) {
            sze[rootb] += sze[roota];
            p[roota] = rootb;
            edges++;
        }
        else {
            sze[roota] += sze[rootb];
            p[rootb] = roota;
            edges++;
        }
        if (edges == n - 1)break;
    }
    dfs(1 , -1 , 1);
    for (int i = 0;i<euler.size();i++)table[i + 1][0] = euler[i];
    for (int j = 1;j < LOG;j++) {
        for (int i = 1;i + (1 << j) - 1 <= euler.size();i++) {
            //cout<<i<<" "<<j<<" "<<table[i][j - 1]<<" "<<table[i + (1 << (j - 1))][j - 1]<<endl;
            if (lvl[table[i][j - 1]] < lvl[table[i + (1 << (j - 1))][j-1]])table[i][j] = table[i][j - 1];
            else table[i][j] = table[i + (1 << (j - 1))][j - 1];
        }
    }
    //return 0;
    for (int j = 1;j < LOG;j++) {
        for (int i = 1;i<=n;i++) {
            par[i][j] = par[par[i][j - 1]][j - 1];
            val[i][j] = min(val[i][j - 1] , val[par[i][j - 1]][j - 1]);
        }
    }
    cin>>q;
    while (q--) {
        cin>>x>>y;
        if (f[x] > f[y])swap(x,y);
        int j = lgg[f[y] - f[x] + 1];
        int node;
        if (lvl[table[f[x]][j]] < lvl[table[f[y] - (1 << j) + 1][j]]) node = table[f[x]][j];
        else node = table[f[y] - (1 << j) + 1][j];
        cout<<lca(x,y,lvl[node])<<endl;
    }
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:114:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0;i<st.size();i++) {
                    ~^~~~~~~~~~
plan.cpp:141:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0;i<euler.size();i++)table[i + 1][0] = euler[i];
                    ~^~~~~~~~~~~~~
plan.cpp:143:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 1;i + (1 << j) - 1 <= euler.size();i++) {
                        ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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