Submission #1084398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084398		khanhphucscratch	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	141 ms	24200 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
vector<vector<int>> components;
int color[1005], sz = 0, color_count[1005], color_link[1005];
/*void build(vector<vector<int>> ans)
{
    int n = ans.size();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) cout<<ans[i][j]<<" ";
        cout<<endl;
    }
}*/
int construct(vector<vector<int>> p)
{
    int n = p.size();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) if(p[i][j] == 3) return 0;
    }
    bool ok = 1;
    for(int i = 0; i < n; i++) if(color[i] == 0){
        color[i] = ++sz;
        queue<int> w; w.push(i);
        vector<int> cur;
        while(w.size() > 0){
            int u = w.front(); w.pop(); cur.push_back(u);
            color_count[color[u]]++;
            for(int v = 0; v < n; v++) if(p[u][v] > 0){
                if(color[v] == 0){
                    color[v] = color[u];
                    w.push(v);
                }
                if(color[v] == color[u]) color_link[color[u]]++;
                else ok = 0;
            }
        }
        components.push_back(cur);
    }
    for(int i = 1; i <= sz; i++) if(color_count[i] * color_count[i] != color_link[i]) ok = 0;
    if(ok == 0) return 0;
    //Solve for each component
    vector<vector<int>> ans(n);
    for(int i = 0; i < n; i++) ans[i].resize(n);
    for(vector<int> c : components){
        memset(color, 0, sizeof(color)); sz = 0;
        memset(color_count, 0, sizeof(color_count));
        memset(color_link, 0, sizeof(color_link));
        vector<vector<int>> small_component;
        for(int i : c) if(color[i] == 0){
            color[i] = ++sz;
            queue<int> w; w.push(i);
            vector<int> cur;
            while(w.size() > 0){
                int u = w.front(); w.pop(); cur.push_back(u);
                color_count[color[u]]++;
                for(int v : c) if(p[u][v] == 1){
                    if(color[v] == 0){
                        color[v] = color[u];
                        w.push(v);
                    }
                    if(color[v] == color[u]) color_link[color[u]]++;
                    else ok = 0;
                }
            }
            if(color_count[sz] * color_count[sz] != color_link[sz]) return 0;
            small_component.push_back(cur);
        }
        if(small_component.size() == 2) return 0;
        int m = small_component.size();
        for(vector<int> d : small_component){
                for(int i = 0; i < d.size()-1; i++){
                ans[d[i]][d[i+1]] = 1;
                ans[d[i+1]][d[i]] = 1;
            }
        }
        if(m > 1){
            for(int i = 0; i < m-1; i++){
                ans[small_component[i][0]][small_component[i+1][0]] = 1;
                ans[small_component[i+1][0]][small_component[i][0]] = 1;
            }
            ans[small_component[m-1][0]][small_component[0][0]] = 1;
            ans[small_component[0][0]][small_component[m-1][0]] = 1;
        }
    }
    build(ans);
    return 1;
}
/*int main()
{
    int n;
    cin>>n;
    vector<vector<int>> p(n);
    for(int i = 0; i < n; i++) p[i].resize(n);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) cin>>p[i][j];
    }
    cout<<construct(p);
}*/

Compilation message (stderr)

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

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4