oj.uz

Submission #934126

# Submission time Handle Problem Language Result Execution time Memory
934126 2024-02-26T20:25:07 Z raul2008487 Connecting Supertrees (IOI20_supertrees) C++17
19 / 100
 179 ms 24312 KB 
#include<bits/stdc++.h>
#include "supertrees.h"
#define ll int
#define in insert
#define pb push_back
#define vl vector<ll>
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
struct DSU{
    vl par;
    vector<vector<ll>> e;
    void init(ll n){
        e.resize(n + 1);
        par.resize(n + 1);
        ll i;
        for(i = 0; i < n; i++){
            e[i].pb(i);
            par[i] = i;
        }
    }
    ll get(ll x){
        if(par[x] == x){
            return x;
        }
        return par[x] = get(par[x]);
    }
    bool connected(ll x, ll y){
        return (get(x) == get(y));
    }
    bool unite(ll a, ll b){
        a = get(a);
        b = get(b);
        if(a == b){return false;}
        if(e[a].size() < e[b].size()){
            swap(a, b);
        }
        par[b] = a;
        for(auto x: e[b]){
            e[a].pb(x);
            par[x] = a;
        }
        e[b].clear();
        return true;
    }
};
int construct(vector<vector<int>> p) {
	DSU dsu1, dsu2;
    ll n = p.size(), i, j;
    dsu1.init(n);
    dsu2.init(n);
    vector<vector<ll>> ans(n, vector<ll> (n, 0));
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            if(p[i][j] == 1){
                dsu1.unite(i, j);
            }
        }
    }
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            if(p[i][j] != 1 && dsu1.connected(i, j)){
                //cout << "1" << endl;
                return 0;
            }
        }
    }
//    for(i = 0; i < n; i++){cout << dsu1.get(i) << ' ';}cout << endl;
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            if(p[i][j] == 2){
                if(dsu2.unite(dsu1.get(i), dsu1.get(j))){
//                    cout << dsu1.get(i) <<  ' ' << dsu1.get(j) << endl;
                }
            }
        }
    }
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            if(i == j){continue;}
            if(p[i][j] != 2 && dsu2.connected(i, j)){
                //cout << "2" << endl;
                return 0;
            }
        }
    }
    vector<bool> used(n, 0), vis(n, 0);
    for(i = 0; i < n; i++){
        ll x = dsu2.get(i);
        if(dsu2.e[x].size() == 2){/*cout << "3" << endl;*/return 0;}
        if(dsu2.e[x].size() > 2 && !used[x]){
            for(j = 0;j < dsu2.e[x].size() - 1; j++){
                ans[dsu2.e[x][j]][dsu2.e[x][j + 1]] = 1;
                ans[dsu2.e[x][j + 1]][dsu2.e[x][j]] = 1;
            }
            ans[dsu2.e[x][0]][dsu2.e[x].back()] = ans[dsu2.e[x].back()][dsu2.e[x][0]] = 1;
            used[x] = 1;
        }
        x = dsu1.get(i);
        if(dsu1.e[x].size() < 2){continue;}
        if(!vis[x]){
            for(j = 0;j < dsu1.e[x].size() - 1; j++){
                ans[dsu1.e[x][j]][dsu1.e[x][j + 1]] = 1;
                ans[dsu1.e[x][j + 1]][dsu1.e[x][j]] = 1;
            }
            ans[dsu1.e[x][0]][dsu1.e[x].back()] = ans[dsu1.e[x].back()][dsu1.e[x][0]] = 1;
            vis[x] = 1;
        }
    }

    build(ans);
    return 1;
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1

*/

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:94:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |             for(j = 0;j < dsu2.e[x].size() - 1; j++){
      |                       ~~^~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:104:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for(j = 0;j < dsu1.e[x].size() - 1; j++){
      |                       ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 344 KB Too many ways to get from 0 to 2, should be 1 found no less than 2
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 344 KB Too many ways to get from 0 to 2, should be 1 found no less than 2
4 Halted 0 ms 0 KB -

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 7 ms 1372 KB Output is correct
9 Correct 154 ms 24072 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 7 ms 1428 KB Output is correct
13 Correct 156 ms 24068 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 82 ms 14204 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 39 ms 6264 KB Output is correct
22 Correct 157 ms 24052 KB Output is correct
23 Correct 159 ms 24196 KB Output is correct
24 Correct 161 ms 24148 KB Output is correct
25 Correct 65 ms 14160 KB Output is correct
26 Correct 64 ms 14336 KB Output is correct
27 Correct 155 ms 24164 KB Output is correct
28 Correct 179 ms 24312 KB Output is correct
29 Correct 62 ms 14164 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Too many ways to get from 1 to 4, should be 1 found no less than 2
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 344 KB Too many ways to get from 0 to 2, should be 1 found no less than 2
4 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 344 KB Too many ways to get from 0 to 2, should be 1 found no less than 2
4 Halted 0 ms 0 KB -