Submission #1290082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290082		win1702	Sightseeing (NOI14_sightseeing)	C++20	25 / 25	2121 ms	131876 KiB

sightseeing

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define MAXN 500005
#define INF 1000000001
#define MOD 1000000007
#define FOR(i, l, r) for (int i = l; i <= r; ++i)
#define FOD(i, r, l) for (int i = r; i >= l; i--)
#define fillchar(a, x) memset(a, x, sizeof(a))
#define rep(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define BIT(x,i) ((x>>i)&1)
#define MASK(i) (1ll<<(i))
#define FILE "tinhcldd"

void fastip(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    if (fopen(FILE".inp","r")){
        freopen(FILE".inp","r",stdin);
        freopen(FILE".out","w",stdout);
    }
}

const int MAX=500006;
const int div2=(MOD+1)/2;


struct Edge{
    int u,v,w;
    bool operator < (const Edge &o) const{
        return w<o.w;
    }
};


int n,m,q;
vector<Edge> E;
vector<int> Q;
int L[MAX], R[MAX], res[MAX];
int par[MAX];
int mx=0;
vector<int> W;

void init_dsu(){
    FOR(i,1,n) par[i]=i;
}

int f(int u){
    return u==par[u]?u:par[u]=f(par[u]);
}

void joint(int u, int v){
    u=f(u);
    v=f(v);
    if (u==v) return;

    if (u>v) swap(u,v);
    par[v]=u;

}

void solve(){
    cin>>n>>m>>q;
    FOR(i,1,m){
        int u,v,w;
        cin>>u>>v>>w;
        E.push_back({u,v,w});
        W.push_back(w);
    }

    sort(W.rbegin(),W.rend());
    W.erase(unique(W.begin(),W.end()),W.end());

    sort(E.rbegin(),E.rend());
    Q.push_back(0);
    FOR(i,1,q){
        int p;
        cin>>p;
        Q.push_back(p);
    }

    FOR(i,1,q) {
        L[i]=0, R[i]=W.size()-1, res[i]=-1;
    }

    while (1){
        vector<vector<int>> check(W.size()+1);
        init_dsu();
        int pro=0;
        FOR(i,1,q){
            if (L[i]<=R[i]){
                int mid=(L[i]+R[i])/2;
                check[mid].push_back(i);
                pro=1;
            }
        }
        if (!pro) break;

        int idE=0;
        for(int imid =0; imid<(int)W.size(); ++imid){
            int mid=W[imid];
            if (check[imid].empty()) continue;
            vector<int> idQ=check[imid];
            while (idE<m && mid<=E[idE].w){
                joint(E[idE].u,E[idE].v);
                idE++;
            }

            for(int id:idQ){
                if (f(Q[id])==1) {
                    res[id]=mid;
                    R[id]=imid-1;
                }
                else{
                    L[id]=imid+1;
                }
            }

        }

    }

    FOR(i,1,q) cout<<res[i]<<'\n';

}


int main(){


    fastip();

    solve();
}

Compilation message (stderr)

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

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