Submission #1290078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290078		G_thang_dizz_lenhi	Sightseeing (NOI14_sightseeing)	C++20	25 / 25	1104 ms	101340 KiB

sightseeing

#include<bits/stdc++.h>
typedef int ii;
typedef long long ll;

using namespace std;

const string name = "TINHCLDD";
const ii MOD = 1e9 + 7;
const ii N = 5e5 + 10;
const ii INF = 1e9 + 237;

ii n, m, q;
vector<pair<ii, ii>> edge[N];
vector<pair<ii, ii>> e[N];
ii dp[N];

void fastscan(int &number)
{
    //variable to indicate sign of input number
    bool negative = false;
    register int c;

    number = 0;

    // extract current character from buffer
    c = getchar();
    if (c=='-')
    {
        // number is negative
        negative = true;

        // extract the next character from the buffer
        c = getchar();
    }

    // Keep on extracting characters if they are integers
    // i.e ASCII Value lies from '0'(48) to '9' (57)
    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48;

    // if scanned input has a negative sign, negate the
    // value of the input number
    if (negative)
        number *= -1;
}

void INP(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if (fopen((name + ".inp").c_str(),"r")){
        freopen((name + ".inp").c_str(),"r",stdin);
        freopen((name + ".out").c_str(),"w",stdout);
    }
    fastscan(n); fastscan(m); fastscan(q);
    // cout << n << " " << m << " " << q << endl;
    ii u, v, len;
    while(m--){
        fastscan(u);
        fastscan(v);
        fastscan(len);
        // cout << u << " " << v << " " << len << endl;
        edge[len].push_back({u, v});
    }
}

struct DSU{
    ii sz;vector<ii> par;

    void init(ii _sz){
        sz = _sz;
        par.resize(sz + 1);
        for (ii i = 1;i <= sz;i++) par[i] = i;
    }

    ii find_par(ii u){
        return (u == par[u] ? u : par[u] = find_par(par[u]));
    }

    bool connect(ii a,ii b){
        a = find_par(a);
        b = find_par(b);
        if (a == b) return false;
        par[a] = b;
        return true;
    }

} DSU;

void dfs(ii u, ii p){
    ii v, len;
    for(auto d : e[u]){
        tie(v, len) = d;
        if (v != p){
            dp[v] = min(dp[u], len);
            dfs(v, u);
        }
    }
}

int main(){
    INP();
    DSU.init(n);
    ii u, v, len;
    for (ii len = N - 1;len >= 0;len--)
    for (auto dir : edge[len]){
        tie(u, v) = dir;
        if (DSU.connect(u, v)){
            e[u].push_back({v, len});
            e[v].push_back({u, len});
//            cerr << u << " " << v << "\n";
        }
    }
    dp[1] = INF;
    dfs(1, 0);
    while(q--){
        fastscan(u);
        cout << dp[u] << "\n";
    }
    return 0;
}

//NGT 1600-2000 cf
//1/200 hard quests

Compilation message (stderr)

sightseeing.cpp: In function 'void fastscan(int&)':
sightseeing.cpp:21:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   21 |     register int c;
      |                  ^
sightseeing.cpp: In function 'void INP()':
sightseeing.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         freopen((name + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen((name + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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