oj.uz

Submission #1041367

# Submission time Handle Problem Language Result Execution time Memory
1041367 2024-08-01T23:41:50 Z HD1 Connecting Supertrees (IOI20_supertrees) C++14
46 / 100
 111 ms 47032 KB 
#include "supertrees.h"
#include<bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ll(x.size())
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAX=1e6;
int f[MAX];
vector<int> adj[MAX];
set<ll> s, c;
int fiend(int u){
    if(f[u] == u)return u;
    return f[u]=fiend(f[u]);
}
void unir(int u,int v){
    int x=fiend(u);
    int y=fiend(v);
    if(x!=y){
        f[x]=y;//x en y
    }
    return;
}
int construct(vector<vector<int>> p) {
    int n = p.size();
    for(int i=0; i<n; i++){
        f[i]=i;
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(p[i][j]==1){
                 unir(i,j);
            }
            if(p[i][j]!=p[j][i])return 0;
        }
    }
    vector<vector<int>> gfo(n,vector<int>(n));
    for(int i=0; i<n; i++){
        fiend(f[i]);
        fiend(i);
        if(f[i]!=i)adj[f[i]].pb(i);// aqui estan cada subarbol de 1 o  mas
        s.insert(f[i]);//representante de cada grupo
    }

    for(auto u:s){//armamos subarboles en la lista dea dj
        for(auto v:adj[u]){
            gfo[v][u]=1;
            gfo[u][v]=1;
        }
    }
    // for(int i=0; i<n; i++){//armamos subarboles
    //     if(sz(adj[i])){
    //         for(int j=0; j+1<sz(adj[i]); j++){
    //             gfo[adj[i][j]][adj[i][j+1]]=1;
    //             gfo[adj[i][j+1]][adj[i][j]]=1;
    //         }
    //     }
    // }
    for(int i=0; i<n; i++){
        adj[i].clear();
        for(int j=0; j<n; j++){
            if(p[i][j]==2){
                 unir(f[i],f[j]);
            }
        }
    } 
    for(auto u:s){
        fiend(f[u]);
        fiend(u);
        if(f[u]!=u)adj[f[u]].pb(u);
        c.insert(f[u]);
    }
    //cout<<sz(c)<<'\n';
    for(auto x:c){
        //cout<<x<<' ';
        adj[x].pb(x);
        for(int i=0; i<sz(adj[x]); i++){
            int v=adj[x][i%sz(adj[x])];
            int u=adj[x][(i+1)%sz(adj[x])];
           if(v!=u){ 
                gfo[v][u]=1;
                gfo[u][v]=1;
            }
        }
    }
    //cout<<'\n';
    // for(auto it:s){//representante de cada grupo
    //     for(int i=0; i<n; i++){//par ver si tiene un 2
    //         if(it==f[i])continue;
    //         if(p[it][i]==2){
    //             gfo[it][f[i]]=1;
    //             gfo[f[i]][it]=1;
    //         }
    //     }
    // }
    build(gfo);
    return 1;
}
/* con fe
9
0 1 1 1 2 2 2 2 2
1 0 1 1 2 2 2 2 2
1 1 0 1 2 2 2 2 2
1 1 1 0 2 2 2 2 2
2 2 2 2 0 2 2 2 2 
2 2 2 2 2 0 2 1 2 
2 2 2 2 2 2 0 2 1
2 2 2 2 2 1 2 0 2
2 2 2 2 2 2 1 2 0
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25180 KB Output is correct
2 Correct 3 ms 25180 KB Output is correct
3 Correct 3 ms 25180 KB Output is correct
4 Correct 3 ms 25180 KB Output is correct
5 Correct 4 ms 25180 KB Output is correct
6 Correct 7 ms 26200 KB Output is correct
7 Correct 99 ms 46836 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25180 KB Output is correct
2 Correct 3 ms 25180 KB Output is correct
3 Correct 3 ms 25180 KB Output is correct
4 Correct 3 ms 25180 KB Output is correct
5 Correct 4 ms 25180 KB Output is correct
6 Correct 7 ms 26200 KB Output is correct
7 Correct 99 ms 46836 KB Output is correct
8 Correct 3 ms 25432 KB Output is correct
9 Correct 4 ms 25180 KB Output is correct
10 Correct 4 ms 25180 KB Output is correct
11 Correct 3 ms 25180 KB Output is correct
12 Correct 7 ms 25948 KB Output is correct
13 Correct 98 ms 47032 KB Output is correct
14 Incorrect 4 ms 25176 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25180 KB Output is correct
2 Correct 3 ms 25180 KB Output is correct
3 Correct 3 ms 25180 KB Output is correct
4 Incorrect 3 ms 25180 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25176 KB Output is correct
2 Correct 3 ms 25180 KB Output is correct
3 Correct 4 ms 25180 KB Output is correct
4 Correct 28 ms 30552 KB Output is correct
5 Correct 104 ms 46932 KB Output is correct
6 Correct 103 ms 46932 KB Output is correct
7 Correct 105 ms 46928 KB Output is correct
8 Correct 4 ms 25176 KB Output is correct
9 Correct 27 ms 30596 KB Output is correct
10 Correct 100 ms 46832 KB Output is correct
11 Correct 109 ms 46916 KB Output is correct
12 Correct 104 ms 46960 KB Output is correct
13 Correct 4 ms 25180 KB Output is correct
14 Correct 3 ms 25180 KB Output is correct
15 Correct 3 ms 25180 KB Output is correct
16 Correct 34 ms 30552 KB Output is correct
17 Correct 111 ms 46932 KB Output is correct
18 Correct 98 ms 46836 KB Output is correct
19 Correct 99 ms 46820 KB Output is correct
20 Correct 102 ms 46928 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25180 KB Output is correct
2 Correct 3 ms 25180 KB Output is correct
3 Correct 3 ms 25180 KB Output is correct
4 Correct 3 ms 25180 KB Output is correct
5 Correct 4 ms 25180 KB Output is correct
6 Correct 7 ms 26200 KB Output is correct
7 Correct 99 ms 46836 KB Output is correct
8 Correct 3 ms 25432 KB Output is correct
9 Correct 4 ms 25180 KB Output is correct
10 Correct 4 ms 25180 KB Output is correct
11 Correct 3 ms 25180 KB Output is correct
12 Correct 7 ms 25948 KB Output is correct
13 Correct 98 ms 47032 KB Output is correct
14 Incorrect 4 ms 25176 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25180 KB Output is correct
2 Correct 3 ms 25180 KB Output is correct
3 Correct 3 ms 25180 KB Output is correct
4 Correct 3 ms 25180 KB Output is correct
5 Correct 4 ms 25180 KB Output is correct
6 Correct 7 ms 26200 KB Output is correct
7 Correct 99 ms 46836 KB Output is correct
8 Correct 3 ms 25432 KB Output is correct
9 Correct 4 ms 25180 KB Output is correct
10 Correct 4 ms 25180 KB Output is correct
11 Correct 3 ms 25180 KB Output is correct
12 Correct 7 ms 25948 KB Output is correct
13 Correct 98 ms 47032 KB Output is correct
14 Incorrect 4 ms 25176 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -