제출 #1111381

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1111381		simuyu	Drivers (BOI24_drivers)	C++14	0 / 100	4 ms	4688 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pl pair<long, long>
#define pll pair<ll, ll>
#define f first
#define s second
#define edge pair<ll, pl>
#define query pair<ll, pair<long, pl> >

// edge is <-time, <from, to>>
// query is <-maxt, <idx, <a, b>>>

long parent[200005];
long depth[200005];
bool ress[200005];

long get_root(long i) {
    while (parent[parent[i]] != parent[i]) {
        parent[i] = parent[parent[i]];
    }
    depth[i] = 1;
    return parent[i];
}

long merge_sets(long i, long j) {
    if (depth[i] < depth[j]) {
        // should add root of i to j, reducing max depth
        long p = get_root(i);
        parent[p] = parent[j]; // this way, they share their root
        depth[p] = depth[i];
        depth[i] = depth[j] + 1;
    } else {
        long p = get_root(j);
        parent[p] = parent[i];
        depth[p] = depth[j];
        depth[j] = depth[i] + 1;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    long N, M, U;
    cin >> N >> M >> U;

    // initialize UFDS
    for (long i=1; i<=N; i++) {
        parent[i] = i;
        depth[i] = 1;
    }

    priority_queue<edge> edges;
    long x, y, t;
    for (long i=0; i<M; i++) {
        // read in the M edges and sort them by weight
        cin >> x >> y >> t;
        edges.push(edge(-t, pl(x, y)));
    }

    // edge is <time, <from, to>>
    // query is <maxt, <idx, <a, b>>>

    long a, b;
    ll maxt;
    priority_queue<query> queries;
    for (long i=0; i<U; i++) {
        cin >> a >> b >> maxt;
        queries.push(query(-maxt, pair<long, pl>(i, pl(a, b))));
    }

    // process the queries (offline)
    ll next_p;
    while (!queries.empty()) {

        //cout << "SOLVING QUERY: " << queries.top().s.f << endl;

        next_p = -queries.top().f;
        //cout << "NEXT P: " << next_p << endl;

        while (!edges.empty()) {
            // see if we should add more edges to UFDS
            if (-edges.top().f <= next_p) {
                // can and should add
                // add
                //cout << "ADDED EDGE (" << edges.top().s.f << ',' << edges.top().s.s << ") FOR " << -edges.top().f << endl;
                merge_sets(edges.top().s.f, edges.top().s.s);
                edges.pop();
            } else {
                break; // shouldn't add anymore
            }
        }

        /*cout << "PARENTS: ";
        for (int i=1; i<=N; i++) {
            cout << parent[i] << ' ';
        }
        cout << endl;*/


        // now try to find
        if (get_root(queries.top().s.s.f) == get_root(queries.top().s.s.s)) {
            // same root, so it's possible
            //cout << "SAME ROOT YAY" << endl;
            ress[queries.top().s.f] = true;
        } else {
            //cout << "DIFF ROOT NOO" << endl;
            ress[queries.top().s.f] = false;
        }

        queries.pop();

    }


    for (int i=0; i<U; i++) {
        if (ress[i]) {
            cout << "TAIP\n";
        } else {
            cout << "NE\n";
        }
    }


    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'long int merge_sets(long int, long int)':
Main.cpp:39:1: warning: no return statement in function returning non-void [-Wreturn-type]
   39 | }
      | ^

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