Submission #198437

#	Time	Username	Problem	Language	Result	Execution time	Memory
198437		model_code	Trucks (LMIO17_sunkvezimiai)	C++17	100 / 100	556 ms	8652 KiB

sunkvezimiai

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1000001;
const int MAXM = 1000001;
const int MAXZ = 1000001;

struct edge {
    int start, end;
    int length;
    
    bool operator <(const edge &that) const {
        return this->length < that.length;
    }
};
edge edges[MAXM];


//Union-find duomenų struktūra
//Ši implementacija naudoja dvi optimizacijas
//Union by rank ir path compression
//Tik viena optimizacija reikalinga norint surinkti visus taškus
int parent[MAXN];
int height[MAXN];

void init(int n) {
    for (int i = 0; i <= n; i++)
        parent[i] = i;
}

//Atlieka path compression
int find(int a) {
    if (a == parent[a])
        return a;
    //Kildami medžiu iki šakninės viršūnės,
    //kiekvieną viršūnę prijungiame tiesiai prie šaknies
    //Todėl pomedžio aukštis sutrumpėja iki 2
    return parent[a] = find(parent[a]);
}

//Atlieka union by rank
void combine(int a, int b) {
    int p_a = find(a);
    int p_b = find(b);
    
    //Prijungiame mažesnį medį prie didesnio
    //Taip medžio aukštis niekada nebus didesnis už log(n)
    if (height[p_a] < height[p_b])
        parent[p_a] = p_b;
    else if(height[p_a] > height[p_b])
        parent[p_b] = p_a;
    else {
        parent[p_a] = p_b;
        height[p_b]++;
    }
    
}

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

struct query {
    int id;
    int start, end;
    int length;
    
    const bool operator<(const query &that) const {
        return this->length < that.length;
    }
};
query queries[MAXZ];
bool results[MAXZ];


int n, m, z;

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false); 
    cin.tie(0);

    cin >> n >> m >> z;
    
    for (int i = 0; i < m; i++) {
        cin >> edges[i].start >> edges[i].end >> edges[i].length;
    }
    for (int i = 0; i < z; i++) {
        queries[i].id = i;
        cin >> queries[i].start >> queries[i].end >> queries[i].length;
    }
    
    sort(edges, edges + m);
    sort(queries, queries + z);
    
    init(n);
    
    //Einame per užklausas didėjimo tvarka
    //Ir prieš atsakydami į užklausą sujungiame visas komponentes
    //Kurios turi briauną trumpesnę arba lygią užklausai
    int cur_edge = 0;
    for (int i = 0; i < z; i++) {
        query &q = queries[i];
        
        while (cur_edge < m && edges[cur_edge].length <= q.length) {
            edge e = edges[cur_edge++];
            combine(e.start, e.end);
        }
        results[q.id] = same(q.start, q.end);
    }
    
    for (int i = 0; i < z; i++)
        cout << (results[i] ? "TAIP" : "NE") << endl;
    return 0;
}

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