Submission #694889

#	Time	Username	Problem	Language	Result	Execution time	Memory
694889		elesis	Sightseeing (NOI14_sightseeing)	C++14	25 / 25	2265 ms	262144 KiB

sightseeing

#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int up=1e6+7;
const int mod=1e9+7;
const int inf=1e18+7;
const int ninf=(-1)*inf;
const int N=5e5+7;
/*
{
    "cmd": ["g++.exe", "-std=c++14", "${file}",
            "-o", "${file_base_name}.exe",
            "&&", "${file_base_name}.exe<inputf.in>outputf.out"],
    "shell":true,
    "working_dir":"$file_path",
    "selector":"source.cpp"
}
*/
/* user preference fix
"trim_automatic_white_space": false,
*/
vector <pii> adj[N];
vector <int> par(N),sz(N,1),ans(N);
vector <bool> vis(N,false);
int findroot(int a)
{
    while(par[a]!=a)
        a=par[a];
    return a;
}
bool unite(int a,int b)
{
    int x=a;
    int y=b;
    a=findroot(a);
    b=findroot(b);
    if(a==b)
    {
        return false;
    }
    if(sz[a]>sz[b])
        swap(a,b);
    par[a]=b;
    sz[b]+=sz[a];
    return true;
}
struct edge
{
  int u,v,c;  
};
bool cmp(edge a, edge b)
{
    return a.c>b.c;
}
vector <int> res(N);
void dfs(int u ,int p,int c)
{
    if(p==0 || p==1)
    {
        res[u]=c;
    }
    else
    {
        res[u]=min(c,res[p]);
    }
    //cout << u << " " << ans[u] << "\n";
    for(auto it:adj[u])
    {
        if(it.ff==p)
        {
            continue;
        }
        dfs(it.ff,u,it.ss);
    }
    //cout << ans[1] << " " << ans[2] << " " << ans[3] << " " << ans[4] << '\n';
}
void solve()
{
    iota(par.begin(),par.end(),0);
    //iota(p.begin(),p.end(),0);
    int n,m,q;
    cin>>n>>m>>q;
    vector <edge> e(m);
    for(int i=0;i<m;i++)
    {
        int u,v,c;
        cin>>u>>v>>c;
        //adj[u].push_back({v,c});
        //adj[v].push_back({u,c});
        e[i].u=u;
        e[i].v=v;
        e[i].c=c;
        //cout << e[i].c << " ";
    }
    //cout << findroot(1) << '\n';
    vector <int> ans(n+1);
    sort(e.begin(),e.end(),cmp);
    for(int i=0;i<m;i++)
    {
        int u=e[i].u;
        int v=e[i].v;
        int c=e[i].c;
        int x=findroot(u);
        int y=findroot(v);
        //cout << x << " " << y << '\n';
        if(unite(x,y))
        {
            adj[u].push_back({v,c});
            adj[v].push_back({u,c});
        }
    }
    /*
    for(int i=1;i<=n;i++)
    {
        cout << i << ": "; 
        for(auto it:adj[i])
        {
            cout << it.ff << ' ';
        }
        cout << '\n';
    }
    */
    //ans[0]=0;
    dfs(1,0,0);
    //cout << ans[3] << '\n';
    while(q--)
    {
        int x;
        cin>>x;
        //cout << x << '\n'
        cout << res[x] << '\n';
        //cout << ans[x] << '\n';
    }
}
signed main(){
    fast
    solve();
}

Compilation message (stderr)

sightseeing.cpp: In function 'bool unite(long long int, long long int)':
sightseeing.cpp:38:9: warning: unused variable 'x' [-Wunused-variable]
   38 |     int x=a;
      |         ^
sightseeing.cpp:39:9: warning: unused variable 'y' [-Wunused-variable]
   39 |     int y=b;
      |         ^

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