oj.uz

Submission #674355

# Submission time Handle Problem Language Result Execution time Memory
674355 2022-12-23T18:28:02 Z Ahmed57 Sightseeing (NOI14_sightseeing) C++14
0 / 25
 3301 ms 68004 KB 
//LCA
#include <bits/stdc++.h>

using namespace std;

const int N=5e5+5;

vector<pair<int,int>> adj[N];

int n,m,q;

//DSU
int pr[500001];
int gs[500001];

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];
    }
}
long long val[500001];
void dfs(int i,int pr,int cnt){
    val[i] = cnt;
    for(auto j:adj[i]){
        if(j.first==pr)continue;
        dfs(j.first,i,min(cnt,j.second));
    }
}
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<<val[x]<<"\n";
    }
}

Compilation message

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

Subtask #1
0 / 4.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 6.0

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

Subtask #4
0 / 10.0

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