Submission #362030

#	Time	Username	Problem	Language	Result	Execution time	Memory
362030		Sorting	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	512 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1000 + 3;

vector<vector<int>> p, answer;
vector<int> adj[N], ans_adj[N], comp;
bool vis[N], c_vis[N];
int cnt[N], n;

void c_dfs(int u, vector<int> &line){
    c_vis[u] = true;
    line.push_back(u);

    for(int to: comp)
        if(!c_vis[to] && p[u][to] == 1 && u != to)
            c_dfs(to, line);
}

void add_edge(int x, int y){
    answer[x][y] = true;
    answer[y][x] = true;
    ans_adj[x].push_back(y);
    ans_adj[y].push_back(x);
}

bool solve_comp(){
    vector<vector<int>> lines;
    for(int i: comp)
        if(!c_vis[i]){
            lines.push_back({});
            c_dfs(i, lines.back());
        }

    for(auto &line: lines)
        for(int i = 0; i < (int)line.size() - 1; ++i)
            add_edge(line[i], line[i + 1]);

    for(int i = 0; i < (int)lines.size(); ++i)
        add_edge(lines[i][0], lines[(i + 1) % lines.size()][0]);

    for(int i = 0; i < lines.size(); ++i)
        for(int j = i + 1; j < lines.size(); ++j)
            for(int i2 = 0; i2 < lines[i].size(); ++i2)
                for(int j2 = 0; j2 < lines[j].size(); ++j2)
                    if(p[lines[i][i2]][lines[j][j2]] != 2)
                        return false;

    for(auto &line: lines)
        for(int i = 0; i < line.size(); ++i)
            for(int j = i + 1; j < line.size(); ++j)
                if(p[line[i]][line[j]] != 1)
                    return false;

    return true;
}

void dfs(int u){
    vis[u] = true;
    comp.push_back(u);

    for(int i = 0; i < n; ++i)
        if(i != u && p[i][u] && !vis[i])
            dfs(i);
}

void clear(){
    fill(vis, vis + n, false);
    fill(c_vis, c_vis + n, false);
    for(int i = 0; i < n; ++i){
        adj[i].clear();
        ans_adj[i].clear();
        cnt[i] = 0;
    }
}

bool solve(){
    clear();

    for(int i = 0; i < n; ++i)
        for(int j = i + 1; j < n; ++j){
            if(p[i][j]){
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }

    for(int i = 0; i < n; ++i)
        if(!vis[i]){
            comp.clear();
            dfs(i);
            if(!solve_comp()) return false;
        }

    return true;
}

int construct(vector<vector<int>> _p) {
    p = _p;
	n = p.size();
    answer.clear();
	answer.resize(n, vector<int>(n, 0));

    if(solve()){
	   build(answer);
	   return 1;
    }
    return 0;
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
*/
/*
2
1 3
3 1
*/

Compilation message (stderr)

supertrees.cpp: In function 'bool solve_comp()':
supertrees.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = 0; i < lines.size(); ++i)
      |                    ~~^~~~~~~~~~~~~~
supertrees.cpp:45:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int j = i + 1; j < lines.size(); ++j)
      |                            ~~^~~~~~~~~~~~~~
supertrees.cpp:46:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             for(int i2 = 0; i2 < lines[i].size(); ++i2)
      |                             ~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:47:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |                 for(int j2 = 0; j2 < lines[j].size(); ++j2)
      |                                 ~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:52:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int i = 0; i < line.size(); ++i)
      |                        ~~^~~~~~~~~~~~~
supertrees.cpp:53:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             for(int j = i + 1; j < line.size(); ++j)
      |                                ~~^~~~~~~~~~~~~

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