oj.uz

Submission #964129

# Submission time Handle Problem Language Result Execution time Memory
964129 2024-04-16T10:50:34 Z SuPythony Connecting Supertrees (IOI20_supertrees) C++17
0 / 100
 1 ms 600 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

class DSU {
    vector<int> par;
    vector<int> siz;

public:
    DSU(int n) {
        par.resize(n);
        iota(par.begin(),par.end(),0);
        siz.assign(n,1);
    }

    int find_set(int u) {
        if (par[u]==u) return u;
        return par[u]=find_set(par[u]);
    }

    bool is_same(int u, int v) {
        return find_set(u)==find_set(v);
    }

    bool unite_set(int u, int v) {
        u=find_set(u);
        v=find_set(v);
        if (u==v) return false;
        if (siz[u]<siz[v]) swap(u,v);
        par[v]=u;
        siz[u]+=siz[v];
        return true;
    }
};

int construct(vector<vector<int>> p) {
    int n = p.size();
    vector<vector<int>> ans(n,vector<int>(n,0));
    DSU dsu1=DSU(n);
    DSU dsu2=DSU(n);
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (i==j) continue;
            if (p[i][j]==1) {
                dsu1.unite_set(i,j);
            }
            if (p[i][j]==2) {
                dsu2.unite_set(i,j);
            }
        }
    }
//    for (int i=0; i<n; i++) {
//        for (int j=0; j<n; j++) {
//            if (p[i][j]==0&&(dsu1.is_same(i,j)||dsu2.is_same(i,j))) {
//                return 0;
//            }
//            if (p[i][j]==1) {
//                if (dsu2.is_same(i,j)) return 0;
//            }
//            if (p[i][j]==2) {
//                if (dsu1.is_same(i,j)) return 0;
//            }
//        }
//    }
    unordered_map<int,vector<int>> m1, m2;
    for (int i=0; i<n; i++) {
        int s2=dsu2.find_set(i);
        int s1=dsu1.find_set(i);
        if (s1==i) {
            if (find(m2[s2].begin(),m2[s2].end(),i)==m2[s2].end()) {
                m2[s2].push_back(i);
            }
        } else {
            if (find(m2[s2].begin(),m2[s2].end(),s1)==m2[s2].end()) {
                m2[s2].push_back(s1);
            }
            if (find(m1[s1].begin(),m1[s1].end(),i)==m1[s1].end()) {
                m1[s1].push_back(i);
            }
        }
    }
    for (auto i: m2) {
        vector<int> s=i.second;
        if (s.size()==1) continue;
        ans[s.front()][s.back()]=1;
        ans[s.back()][s.front()]=1;
        for (int j=0; j<s.size()-1; j++) {
            ans[s[j]][s[j+1]]=1;
            ans[s[j+1]][s[j]]=1;
        }
        for (int j=0; j<s.size(); j++) {
            if (m1.count(s[j])) {
                vector<int> s2=m1[s[j]];
                for (int k: s2) {
                    if (k!=s[j]) {
                        ans[k][s[j]]=1;
                        ans[s[j]][k]=1;
                    }
                }
            }
        }
    }
    build(ans);
    return 1;
}

Compilation message

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 600 KB Too few ways to get from 0 to 1, should be 1 found 0
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 600 KB Too few ways to get from 0 to 1, should be 1 found 0
3 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Incorrect 0 ms 348 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 348 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Incorrect 0 ms 348 KB Too few ways to get from 1 to 2, should be 1 found 0
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 600 KB Too few ways to get from 0 to 1, should be 1 found 0
3 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 600 KB Too few ways to get from 0 to 1, should be 1 found 0
3 Halted 0 ms 0 KB -