oj.uz

Submission #862664

# Submission time Handle Problem Language Result Execution time Memory
862664 2023-10-18T18:36:27 Z HossamHero7 Kutije (COCI21_kutije) C++14
70 / 70
 121 ms 13476 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
struct dsu{
    int n;
    vector<int> par;
    dsu(int _n){
        n = _n;
        par.resize(n);
        iota(par.begin(),par.end(),0);
    }
    int getP(int node){
        if(par[node] == node) return node;
        return par[node] = getP(par[node]);
    }
    void add(int u,int v){
        int a = getP(u), b = getP(v);
        if(a == b) return;
        par[b] = a;
    }
};
void solve(){
    int n,m,q;
    cin>>n>>m>>q;
    vector<vector<int>> v(m,vector<int>(n));
    for(auto &i:v) for(auto &j:i) cin>>j;
    dsu ds(n);
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            ds.add(j,v[i][j]-1);
        }
    }
    while(q--){
        int a,b;
        cin>>a>>b;
        a --,b --;
        cout<<(ds.getP(a) == ds.getP(b) ? "DA" : "NE")<<endl;
    }
    
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 5648 KB Output is correct
2 Correct 57 ms 4944 KB Output is correct
3 Correct 53 ms 4688 KB Output is correct
4 Correct 71 ms 5596 KB Output is correct
5 Correct 80 ms 5580 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 536 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 532 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 468 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 536 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 532 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 532 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 5648 KB Output is correct
2 Correct 57 ms 4944 KB Output is correct
3 Correct 53 ms 4688 KB Output is correct
4 Correct 71 ms 5596 KB Output is correct
5 Correct 80 ms 5580 KB Output is correct
6 Correct 1 ms 536 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 532 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 532 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 115 ms 13328 KB Output is correct
27 Correct 121 ms 13340 KB Output is correct
28 Correct 95 ms 11092 KB Output is correct
29 Correct 111 ms 12880 KB Output is correct
30 Correct 103 ms 11604 KB Output is correct
31 Correct 102 ms 11604 KB Output is correct
32 Correct 112 ms 13476 KB Output is correct
33 Correct 117 ms 13352 KB Output is correct
34 Correct 115 ms 13344 KB Output is correct
35 Correct 119 ms 13464 KB Output is correct