Submission #674349

#	Time	Username	Problem	Language	Result	Execution time	Memory
674349		Ahmed57	Sightseeing (NOI14_sightseeing)	C++14	15 / 25	2931 ms	135888 KiB

sightseeing

//LCA
#include <bits/stdc++.h>

using namespace std;

const int N=1e5+5;

vector<pair<int,int>> adj[N];
long long P[N][18],mi[N][18];
long long hi[N];
int n,m,q;

void dfs(int node,int pa,int ed){
    P[node][0]=pa;
    hi[node]=hi[pa]+1;
    mi[node][0] = ed;
    for(int k=1;k<=17;k++){
        P[node][k]=P[P[node][k-1]][k-1];
        mi[node][k] = min(mi[node][k-1],mi[P[node][k-1]][k-1]);
    }
    for(auto i:adj[node]){
        if(i.first==pa) continue;
        dfs(i.first,node,i.second);
    }
}

long long lca(int x,int y)
{
    long long mii = 1e18;
    if(hi[x]<hi[y]) swap(x,y);
    for(int k=17;k>=0;k--)
    {
        if(hi[x]-(1<<k) >= hi[y]){
            mii = min(mii,mi[x][k]);
            x=P[x][k];
        }
    }
    if(x==y) return mii;
    for(int k=17;k>=0;k--)
    {
        if(P[x][k] != P[y][k]){
            mii = min(mii,mi[x][k]);
            mii = min(mii,mi[y][k]);
            x=P[x][k],y=P[y][k];
        }
    }
    return min({mii,mi[x][0],mi[y][0]});
}
//DSU
int pr[100001];
int gs[100001];

int findleader(int x){
    if(pr[x]==x){
        return x;
    }
    return pr[x] = findleader(pr[x]);
}
bool samegroup(int x,int y){
    int led1 = findleader(x);
    int led2 = findleader(y);
    return led1==led2;
}
void mergegroup(int x,int y){
    int led1 = findleader(x);
    int led2 = findleader(y);
    if(led1==led2)return;
    if(gs[led1]>gs[led2]){
        pr[led2]=led1;
        gs[led1]+=gs[led2];
    }else{
        pr[led1]=led2;
        gs[led2]+=gs[led1];
    }
}
int main()
{
    for(int i = 0;i<N;i++)pr[i] = i , gs[i] = 1;
    cin>>n>>m>>q;
    vector<pair<int,pair<int,int>>>v;
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        v.push_back({z,{x,y}});
    }
    sort(v.begin(),v.end());
    for(int i = v.size()-1;i>=0;i--){
        if(!samegroup(v[i].second.first,v[i].second.second)){
            mergegroup(v[i].second.first,v[i].second.second);
            adj[v[i].second.first].push_back({v[i].second.second,v[i].first});
            adj[v[i].second.second].push_back({v[i].second.first,v[i].first});
        }
    }
    dfs(1,0,0);
    while(q--){
        int x;
        cin>>x;
        cout<<lca(1,x)<<"\n";
    }
}

Compilation message (stderr)

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:78:33: warning: iteration 100001 invokes undefined behavior [-Waggressive-loop-optimizations]
   78 |     for(int i = 0;i<N;i++)pr[i] = i , gs[i] = 1;
      |                           ~~~~~~^~~
sightseeing.cpp:78:20: note: within this loop
   78 |     for(int i = 0;i<N;i++)pr[i] = i , gs[i] = 1;
      |                   ~^~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 0 / 10