Submission #1246697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246697		vukhacminh	Sightseeing (NOI14_sightseeing)	C++20	25 / 25	1380 ms	128436 KiB

sightseeing

/**
*    Author :  Vu Khac Minh
*    Created : 19.01.2024
**/
#include <bits/stdc++.h>
#define MASK(x) ((1ll) << (x))
#define BIT(x, i) (((x) >> (i)) & (1))
#define c_bit(i) __builtin_popcountll(i)
#define SET_ON(x, i) ((x) | MASK(i))
#define SET_OFF(x, i) ((x) & ~MASK(i))
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = " << (val) << "] "
#define ll long long
using namespace std;
const int maxn = 1e6 + 5;
const int mod = 1e9+7;
void file()
{
    #define Task "ROUNDPRI"
    if(fopen(Task".inp","r"))
    {
        freopen(Task".inp","r",stdin);
        freopen(Task".out","w",stdout);
    }
}
int n,m,a[maxn],nquery;
struct DSU
{
    vector<int> par,lab;
    DSU(int n) : par(n+2),lab(n+2){};
    void make_set(int i)
    {
        par[i] = i;
        lab[i] = 1;
    }
    int getroot(int u)
    {
        if(u == par[u]) return u;
        return par[u] = getroot(par[u]);
    }
    bool Joint(int u,int v)
    {
        u=  getroot(u);
        v = getroot(v);
        if(u == v) return false;
        if(lab[u]<lab[v]) swap(u,v);
        lab[u]+=lab[v];
        par[v] = u;
        return true;
    }
};
struct E
{
    int u,v,w;
};
vector<E> edge;
bool cmp(E &x,E &y)
{
    return x.w>y.w;
}
int res[maxn];
vector<pair<int,int>> adj[maxn];
void dfs(int u,int par)
{
    for(auto v : adj[u])
        if(v.first != par)
    {
        res[v.first] = min(res[u],v.second);
        dfs(v.first,u);
    }
}
void solve()
{
    cin>>n>>m>>nquery;
    DSU dsu(n);
    FOR(i,1,n)
    {
        res[i] = 1e9;
        dsu.make_set(i);
    }
    for(int i = 1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        edge.push_back({u,v,w});
    }
    sort(edge.begin(),edge.end(),cmp);
    for(auto x : edge)
    {
        int u = x.u,v = x.v,w = x.w;
        if(dsu.Joint(u,v))
        {
            adj[u].push_back({v,w});
            adj[v].push_back({u,w});
        }
    }
    res[1] = 1e9;
    dfs(1,-1);
    res[1] = 0;
    while(nquery--)
    {
        int x;
        cin>>x;
        cout<<res[x]<<'\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest = 1;
    file();
    //cin >> ntest;
    while (ntest--)
    {
        solve();
    }

    return 0;
}

Compilation message (stderr)

sightseeing.cpp: In function 'void file()':
sightseeing.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen(Task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen(Task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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