Submission #1269220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269220		herominhsteve	Drivers (BOI24_drivers)	C++20	100 / 100	142 ms	27884 KiB

Main

#include<bits/stdc++.h>
#define el '\n'
#define FNAME "Drivers"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset((x),(n),sizeof(x));
using namespace std;
const long long MOD = (long long) 1e9+7;
template<class X,class Y> bool minimize(X &a,Y b){if (a>b){a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){if (a<b){a=b; return true;} return false;}

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

const int MAXN = 2e5 + 5;

struct Query{
    int u,v,p;
    Query(): u(0),v(0),p(0) {}
    Query(int U,int V,int Q): u(U), v(V), p(Q) {}
};

struct Edges{
    int u,v,w;
    Edges(): u(0), v(0), w(0) {}
    Edges(int U,int V,int W): u(U),v(V),w(W) {}
    bool operator < (const Edges &other) const {
        return w < other.w;
    }
};

struct DSU{
    int n;
    vector<int> parent,power;
    DSU(int N=0){
        n=N;
        if (n>0){
            parent.assign(n+1,0);
            power.assign(n+1,1);
        }
    }
    void make_set(){
        for (int i=1;i<=n;i++){
            parent[i] = i;
            power[i] = 1;
        }
    }
    int find(int u){
        if (u==parent[u]) return u;
        return parent[u] = find(parent[u]);
    }
    bool Union(int u,int v){
        u = find(u);
        v = find(v);
        if (u==v) return false;
        if (power[u] < power[v]) swap(u,v);
        parent[v] = u;
        power[u] += power[v];
        return true;
    }
};

int n,m,q;
vector<Edges> edge;
vector<Query> query;
vector<int> eByW[MAXN];
vector<int> qByW[MAXN];
int maxW;

void init(){
    cin>>n>>m>>q;
    vector<int> compress;
    for (int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        edge.emplace_back(u,v,w);
        compress.push_back(w);
    }
    for (int i=0;i<q;i++){
        int u,v,p;
        cin>>u>>v>>p;
        query.emplace_back(u,v,p);
        compress.push_back(p);
    }
    sort(allof(compress));
    compress.resize(unique(allof(compress))-compress.begin());
    maxW = compress.size() + 1;
    for (int i=0;i<m;i++){
        int t = lower_bound(allof(compress),edge[i].w) - compress.begin() + 1;
        edge[i].w = t;
        eByW[t].push_back(i);
    }
    for (int i=0;i<q;i++){
        int t = lower_bound(allof(compress),query[i].p) - compress.begin() + 1;
        query[i].p = t;
        qByW[t].push_back(i);
    }
}

void sol(){
    DSU dsu(n);
    dsu.make_set();
    vector<bool> res(q,0);
    for (int w=0;w<=maxW;w++){
        for (int ID : eByW[w]) dsu.Union(edge[ID].u,edge[ID].v);
        for (int ID : qByW[w]) res[ID] = (dsu.find(query[ID].u)==dsu.find(query[ID].v));
    }
    for (bool x : res) if (x) cout<<"TAIP\n"; else cout<<"NE\n";
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 23 / 23
• Subtask 5: 45 / 45