oj.uz

Submission #1111381

# Submission time Handle Problem Language Result Execution time Memory
1111381 2024-11-12T07:57:00 Z simuyu Drivers (BOI24_drivers) C++14
0 / 100
 4 ms 4688 KB 
#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;
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 4688 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 4688 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 4688 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 4688 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 4688 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -