Submission #641746

#	Time	Username	Problem	Language	Result	Execution time	Memory
641746		pls33	Trucks (LMIO17_sunkvezimiai)	C++17	100 / 100	157 ms	15172 KiB

sunkvezimiai

#include <bits/stdc++.h>

using namespace std;

using p32 = pair<int, int>;
using p64 = pair<int64_t, int64_t>;
using vi16 = vector<int16_t>;
using vi32 = vector<int>;
using vi64 = vector<int64_t>;
using vp32 = vector<p32>;
using vp64 = vector<p64>;
using vvi32 = vector<vi32>;
using vvi64 = vector<vi64>;
using vvp32 = vector<vp32>;
using vvp64 = vector<vp64>;


struct edge {
    int a, b;
    int time;
};

struct query : public edge {
    int pos;
};

int find_set(int a, vi32 &parents){
    if(a != parents[a]){
        parents[a] = find_set(parents[a], parents);
    }

    return parents[a];
}

void unite_sets(int a, int b, vi32 &parents, vi32 &ranks){
    a = find_set(a, parents);
    b = find_set(b, parents);

    if(a == b){
        return;
    }

    if(ranks[a] < ranks[b]){
        swap(a, b);
    }

    parents[b] = a;
    ranks[a] += ranks[b];
}


int eval_query(query &q, vi32 &parents, vi32 &ranks,
    int &prev_edge, vector<edge> &edges)
{
    if(find_set(q.a, parents) == find_set(q.b, parents)){
        return 1;
    }

    auto last_iter = upper_bound(edges.begin() + prev_edge, edges.end(), q, 
    [](const edge &a, const edge &b)
    {
        return a.time < b.time;
    });

    int last_edge = min(int(last_iter - edges.begin()), int(edges.size()));

    if(last_edge <= prev_edge){
        return 0;
    }

    for(int i = prev_edge; i < last_edge; i++){
        unite_sets(edges[i].a, edges[i].b, parents, ranks);
    }
    
    prev_edge = last_edge;
    return find_set(q.a, parents) == find_set(q.b, parents);
}

int main()
{
    #ifndef _AAAAAAAAA
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #else
    freopen("sunk.in", "r", stdin);
    #endif

    int cities, roads, queries;
    cin >> cities >> roads >> queries;

    vector<edge> e(roads);
    for(int i = 0; i < roads; i++){
        cin >> e[i].a >> e[i].b >> e[i].time;

        e[i].a--;
        e[i].b--;
    }

    vector<query> q(queries);
    for(int i = 0; i < queries; i++){
        int a, b, time;
        cin >> q[i].a >> q[i].b >> q[i].time;

        q[i].a--;
        q[i].b--;
        q[i].pos = i;
    }

    sort(e.begin(), e.end(), [](edge &a, edge &b)
    {
        return a.time < b.time;
    });

    sort(q.begin(), q.end(), [](query &a, query &b)
    {
        return a.time < b.time;
    });

    vi32 ranks(cities, 1);
    vi32 parents(cities);
    iota(parents.begin(), parents.end(), 0);

    int last_edge = 0;
    for(auto &a : q){
        a.a = eval_query(a, parents, ranks, last_edge, e);
    }

    sort(q.begin(), q.end(), [](query &a, query &b)
    {
        return a.pos < b.pos;
    });

    for(auto &a : q){
        if(a.a){
            cout << "TAIP" << '\n';
        }
        else {
            cout << "NE" << '\n';
        }
    }

    return 0;
}

Compilation message (stderr)

sunkvezimiai.cpp: In function 'int main()':
sunkvezimiai.cpp:101:13: warning: unused variable 'a' [-Wunused-variable]
  101 |         int a, b, time;
      |             ^
sunkvezimiai.cpp:101:16: warning: unused variable 'b' [-Wunused-variable]
  101 |         int a, b, time;
      |                ^
sunkvezimiai.cpp:101:19: warning: unused variable 'time' [-Wunused-variable]
  101 |         int a, b, time;
      |                   ^~~~

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