oj.uz

Submission #198437

# Submission time Handle Problem Language Result Execution time Memory
198437 2020-01-26T03:30:04 Z model_code Trucks (LMIO17_sunkvezimiai) C++17
100 / 100
 556 ms 8652 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 461 ms 4712 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 7 ms 504 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 8 ms 376 KB Output is correct
7 Correct 32 ms 768 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 8 ms 376 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 28 ms 760 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 6 ms 376 KB Output is correct
14 Correct 8 ms 504 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 7 ms 376 KB Output is correct
18 Correct 7 ms 504 KB Output is correct
19 Correct 10 ms 504 KB Output is correct
20 Correct 10 ms 504 KB Output is correct
21 Correct 19 ms 504 KB Output is correct
22 Correct 6 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 7 ms 376 KB Output is correct
7 Correct 7 ms 504 KB Output is correct
8 Correct 10 ms 504 KB Output is correct
9 Correct 10 ms 504 KB Output is correct
10 Correct 19 ms 504 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 461 ms 4712 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 7 ms 504 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 8 ms 376 KB Output is correct
7 Correct 32 ms 768 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 8 ms 376 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 28 ms 760 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 6 ms 376 KB Output is correct
14 Correct 8 ms 504 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 7 ms 376 KB Output is correct
18 Correct 7 ms 504 KB Output is correct
19 Correct 10 ms 504 KB Output is correct
20 Correct 10 ms 504 KB Output is correct
21 Correct 19 ms 504 KB Output is correct
22 Correct 6 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 461 ms 4712 KB Output is correct

Subtask #5
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 8364 KB Output is correct
2 Correct 36 ms 1020 KB Output is correct
3 Correct 26 ms 888 KB Output is correct
4 Correct 26 ms 1144 KB Output is correct
5 Correct 39 ms 1020 KB Output is correct
6 Correct 33 ms 888 KB Output is correct
7 Correct 319 ms 6392 KB Output is correct
8 Correct 37 ms 1012 KB Output is correct
9 Correct 531 ms 8652 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 8 ms 376 KB Output is correct
12 Correct 7 ms 376 KB Output is correct
13 Correct 7 ms 504 KB Output is correct
14 Correct 6 ms 376 KB Output is correct
15 Correct 8 ms 376 KB Output is correct
16 Correct 32 ms 768 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 8 ms 376 KB Output is correct
19 Correct 6 ms 376 KB Output is correct
20 Correct 28 ms 760 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 6 ms 376 KB Output is correct
23 Correct 8 ms 504 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 7 ms 376 KB Output is correct
27 Correct 7 ms 504 KB Output is correct
28 Correct 10 ms 504 KB Output is correct
29 Correct 10 ms 504 KB Output is correct
30 Correct 19 ms 504 KB Output is correct
31 Correct 6 ms 376 KB Output is correct
32 Correct 5 ms 376 KB Output is correct
33 Correct 5 ms 376 KB Output is correct
34 Correct 5 ms 376 KB Output is correct
35 Correct 461 ms 4712 KB Output is correct