oj.uz

Submission #1085871

# Submission time Handle Problem Language Result Execution time Memory
1085871 2024-09-08T23:06:33 Z sergio_sak Drivers (BOI24_drivers) C++14
10 / 100
 237 ms 7136 KB 
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <bit>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <time.h>
#include <random>
#include <inttypes.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

using namespace __gnu_pbds;

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("O3,Ofast")

#define EPS 1e-9
#define PI acos(-1)
#define MAXN 200005
#define MOD 1'000'000'007
#define INF 1'000'000'000'000

#define ll int64_t
#define int int32_t
#define short int16_t

#define si(n) if(scanf("%d", &n))
#define sl(n) scanf("%ld", &n);
#define sc(n) scanf("%c", &n);
#define sf(n) scanf("%f", &n);
#define slf(n) scanf("%lf", &n);

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define dbg(x) std::cerr << #x << ": " << x << std::endl;

typedef std::set<int> si;
typedef std::set<ll> sll;
typedef std::pair<int, int> pi;
typedef std::pair<ll, ll> pll;
typedef std::vector<int> vi;
typedef std::vector<ll> vll;
typedef std::vector<std::vector<int>> dvi;
typedef std::vector<std::vector<ll>> dvll;
typedef std::unordered_map<int , int> mi;
typedef std::unordered_map<ll , ll> mll;

ll gcd(ll a, ll b) {return (b == 0) ? a : gcd(b, a%b);}
ll lcm(ll a, ll b) {return a/gcd(a, b) * b;}

int N, M, Q;
bool res[MAXN];
int par[MAXN], size[MAXN];
std::vector<std::tuple<int, int, int>> edges;
std::vector<std::tuple<int, int, int, int>> queries;

//Union Psajimo
void DSU() {
    for(int i = 0; i <= N; ++i) {
        par[i] = i;
        size[i] = 1;
    }
}

int find(int a) {
    if(a == par[a]) return a;
    return par[a] = find(par[a]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);

    if(size[a] < size[b]) std::swap(a, b);
    par[b] = a;
    size[a] += size[b];
}

bool same(int a, int b) {
    return find(a) == find(b);
}

signed main()
{
    // freopen("file.out", "w", stdout);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
    std::cin>>N>>M>>Q;

    for(int i = 0; i < M; ++i) {
        int u, v, w;
        std::cin>>u>>v>>w;
        edges.pb({w, u, v});
    }

    for(int i = 0; i < Q; ++i) {
        int a, b, p;
        std::cin>>a>>b>>p;
        queries.pb({p, a, b, i});
    }

    std::sort(all(edges));
    std::sort(all(queries));

    DSU();

    int a, b, p, id, indx = 0;
    int u, v, w = 0;
    std::tie(w, u, v) = edges[0];
    for(int i = 0; i < Q; ++i) {
        std::tie(p, a, b, id) = queries[i];
        
        while(w <= p && indx < M) {
            std::tie(w, u, v) = edges[indx++];
            // if(!same(u, v)) 
                unite(u, v);
        }

        res[id] = same(a, b);
    }

    for(int i = 0; i < Q; ++i) {
        if(res[i]) std::cout<<"TAIP"<<std::endl;
        else std::cout<<"NE"<<std::endl;
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 237 ms 7136 KB Output is correct

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 472 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Incorrect 1 ms 600 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 237 ms 7136 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 856 KB Output is correct
9 Incorrect 3 ms 604 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 237 ms 7136 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 472 KB Output is correct
9 Correct 2 ms 480 KB Output is correct
10 Incorrect 1 ms 600 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 237 ms 7136 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 472 KB Output is correct
9 Correct 2 ms 480 KB Output is correct
10 Incorrect 1 ms 600 KB Output isn't correct
11 Halted 0 ms 0 KB -