oj.uz

Submission #720652

# Submission time Handle Problem Language Result Execution time Memory
720652 2023-04-08T19:53:01 Z Toxtaq Connecting Supertrees (IOI20_supertrees) C++17
11 / 100
 208 ms 22104 KB 
#ifndef SUPERTREES_H_INCLUDED
#define SUPERTREES_H_INCLUDED
#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
struct DSU{
    vector<int>par;
    vector<vector<int>>parV;
    DSU(int n){
        par.assign(n, -1);
        parV.resize(n);
        for(int i = 0;i < n;++i)parV[i].push_back(i);
    }
    int FindRep(int u){
        if(par[u] < 0)return u;
        return par[u] = FindRep(par[u]);
    }
    void Union(int u, int v){
        u = FindRep(u);
        v = FindRep(v);
        if(u == v)return;
        if(par[u] > par[v])swap(u, v);
        par[u] += par[v];
        par[v] = u;
        for(int i : parV[v]){
            parV[u].push_back(i);
        }
    }
    bool IsConnected(int u, int v){
        u = FindRep(u);
        v = FindRep(v);
        return (u == v);
    }
};
void build(vector<vector<int>>b);
int construct(vector<vector<int>>p){
    int n = p.size();
    vector<vector<int>>ans(n, vector<int>(n));
    DSU dsu1(n);
    for(int i = 0;i < n;++i){
        for(int j = 0;j < n;++j){
            if(i != j && p[i][j])dsu1.Union(i, j);
        }
    }
    vector<bool>chosen(n);
    for(int i = 0;i < n;++i){
        if(chosen[i])continue;
        vector<int>components, ones, twos;
        swap(components, dsu1.parV[dsu1.FindRep(i)]);
        for(int j : components){
            chosen[j] = 1;
            int cnt = 0;
            for(int z = 0;z < n;++z){
                if(p[j][z] == 1){
                    cnt++;
                }
            }
            if(cnt == 1)twos.push_back(j);
            else ones.push_back(j);
        }
//        cout << i << ": \n";
//        cout << "ones: ";
//        for(int j : ones)cout << j << " ";
//        cout << "\ntwos: ";
//        for(int j : twos)cout << j << " ";
//        cout << '\n';
        for(int j = 1;j < ones.size();++j){
            ans[ones[j - 1]][ones[j]] = 1;
            ans[ones[j]][ones[j - 1]] = 1;
        }
        for(int j = 1;j < twos.size();++j){
            ans[twos[j - 1]][twos[j]] = 1;
            ans[twos[j]][twos[j - 1]] = 1;
        }
        if(!ones.size() && twos.size()){
            if(twos.size() > 1)ans[twos[0]][twos.back()] = ans[twos.back()][twos[0]] = 1;
        }
        else if(ones.size() > 1 && twos.size() > 2){
            ans[ones.back()][twos[0]] = 1;
            ans[twos[0]][ones.back()] = 1;
            ans[twos.back()][ones.back()] = 1;
            ans[ones.back()][twos.back()] = 1;
        }
    }
//    for(int i = 0;i < n;++i){
//        for(int j = i + 1;j < n;++j){
//            if(ans[i][j])cout << i << ", " << j << '\n';
//        }
//    }
    build(ans);
    return 1;
}


#endif // SUPERTREES_H_INCLUDED

Compilation message

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 8 ms 1108 KB Output is correct
7 Correct 164 ms 22104 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 8 ms 1108 KB Output is correct
7 Correct 164 ms 22104 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 11 ms 1124 KB Output is correct
13 Correct 163 ms 21968 KB Output is correct
14 Incorrect 0 ms 212 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 45 ms 5752 KB Output is correct
5 Correct 195 ms 22028 KB Output is correct
6 Correct 172 ms 21996 KB Output is correct
7 Correct 202 ms 22016 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 42 ms 5768 KB Output is correct
10 Correct 181 ms 22020 KB Output is correct
11 Correct 175 ms 22072 KB Output is correct
12 Correct 208 ms 22060 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Incorrect 0 ms 212 KB Too few ways to get from 0 to 1, should be 2 found 0
16 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 8 ms 1108 KB Output is correct
7 Correct 164 ms 22104 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 11 ms 1124 KB Output is correct
13 Correct 163 ms 21968 KB Output is correct
14 Incorrect 0 ms 212 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 8 ms 1108 KB Output is correct
7 Correct 164 ms 22104 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 11 ms 1124 KB Output is correct
13 Correct 163 ms 21968 KB Output is correct
14 Incorrect 0 ms 212 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -