oj.uz

Submission #720655

# Submission time Handle Problem Language Result Execution time Memory
720655 2023-04-08T20:11:39 Z Toxtaq Connecting Supertrees (IOI20_supertrees) C++17
11 / 100
 177 ms 22032 KB 
#ifndef SUPERTREES_H_INCLUDED
#define SUPERTREES_H_INCLUDED
#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
struct DSU{
    vector<int>par;
    DSU(int n){
        par.assign(n, -1);
    }
    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;
    }
    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);
    vector<int>oneortwo(n);
    for(int i = 0;i < n;++i){
        int cnt = 0;
        for(int j = 0;j < n;++j){
            if(i != j && p[i][j])dsu1.Union(i, j);
            cnt += (p[i][j] == 1);
        }
        if(cnt == 1)oneortwo[i] = 2;
        else oneortwo[i] = 1;
    }
    vector<bool>chosen(n);
    for(int i = 0;i < n;++i){
        int par = dsu1.FindRep(i);
        if(chosen[i])continue;
        vector<int>ones, twos;
        for(int j = 0;j < n;++j){
            int node = dsu1.FindRep(j);
            if(dsu1.FindRep(j) == par){
                chosen[j] = 1;
                if(oneortwo[j] == 2)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() && (int)twos.size() > 1){
            ans[twos[0]][twos.back()] = ans[twos.back()][twos[0]] = 1;
        }
        else if(ones.size() && (int)twos.size() > 1){
            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:50:17: warning: unused variable 'node' [-Wunused-variable]
   50 |             int node = dsu1.FindRep(j);
      |                 ^~~~
supertrees.cpp:63:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j = 1;j < ones.size();++j){
      |                       ~~^~~~~~~~~~~~~
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 < 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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 7 ms 1108 KB Output is correct
7 Correct 164 ms 22024 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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 7 ms 1108 KB Output is correct
7 Correct 164 ms 22024 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 7 ms 1108 KB Output is correct
13 Correct 173 ms 21944 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 0 ms 212 KB Output is correct
3 Correct 0 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 43 ms 5712 KB Output is correct
5 Correct 166 ms 22020 KB Output is correct
6 Correct 164 ms 22020 KB Output is correct
7 Correct 174 ms 22016 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 42 ms 5672 KB Output is correct
10 Correct 166 ms 22028 KB Output is correct
11 Correct 162 ms 21968 KB Output is correct
12 Correct 177 ms 22032 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 276 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Incorrect 42 ms 5708 KB Too few ways to get from 0 to 24, should be 2 found 1
17 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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 7 ms 1108 KB Output is correct
7 Correct 164 ms 22024 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 7 ms 1108 KB Output is correct
13 Correct 173 ms 21944 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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 7 ms 1108 KB Output is correct
7 Correct 164 ms 22024 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 7 ms 1108 KB Output is correct
13 Correct 173 ms 21944 KB Output is correct
14 Incorrect 0 ms 212 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -