Submission #309048

#	Time	Username	Problem	Language	Result	Execution time	Memory
309048		tjdgus4384	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	287 ms	34168 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
vector<int> graph[1001], trees[1001];
vector<vector<int> > b, P, newp;
vector<int> v[1001];
vector<int> sametree;
bool visited[1001];
 
void dfs(int x, int cnt){
    graph[cnt].push_back(x);
    for(int i = 0;i < v[x].size();i++){
        if(visited[v[x][i]]) continue;
        visited[v[x][i]] = true;
        dfs(v[x][i], cnt);
    }
}
 
void make_tree(int x){
    for(int i = 0;i < v[x].size();i++){
        if(visited[v[x][i]]) continue;
        if(P[x][v[x][i]] != 1) continue;
        visited[v[x][i]] = true;
        sametree.push_back(v[x][i]);
        make_tree(v[x][i]);
        b[x][v[x][i]] = 1;
        b[v[x][i]][x] = 1;
    }
}

int construct(vector<vector<int> > p){
    P = p;
    b.resize(p.size());
    newp.resize(p.size());
    for(int i = 0;i < p.size();i++){
        b[i].resize(p.size());
        newp[i].resize(p.size());
        for(int j = 0;j < p.size();j++){
            if(i == j) continue;
            if(p[i][j]) v[i].push_back(j);
            if(p[i][j] == 3) return 0;
        }
    }
    int cnt = 0;
    for(int i = 0;i < p.size();i++){
        if(visited[i]) continue;
        visited[i] = true;
        dfs(i, cnt); cnt++;
    }
    for(int i = 0;i < p.size();i++) visited[i] = false;
    for(int i = 0;i < cnt;i++){
        vector<int> nv;
        for(int j = 0;j < graph[i].size();j++){
            if(visited[graph[i][j]]) continue;
            visited[graph[i][j]] = true;
            sametree.push_back(graph[i][j]);
            make_tree(graph[i][j]);
            for(int x1 = 0;x1 < sametree.size();x1++){
                for(int x2 = 0;x2 < sametree.size();x2++){
                    if(x1 == x2) continue;
                    newp[sametree[x1]][sametree[x2]] = newp[sametree[x2]][sametree[x1]] = 1;
                }
            }
            sametree.clear();
            nv.push_back(graph[i][j]);
        }
        if(nv.size() <= 1) continue;
        if(nv.size() <= 2) return 0;
        for(int j = 0;j < nv.size() - 1;j++){
            b[nv[j]][nv[j+1]] = 1;
            b[nv[j+1]][nv[j]] = 1;
        }
        for(int x1 = 0;x1 < nv.size();x1++){
            for(int x2 = 0;x2 < graph[i].size();x2++){
                if(nv[x1] == graph[i][x2]) continue;
                if(newp[nv[x1]][graph[i][x2]]) continue;
                newp[nv[x1]][graph[i][x2]] = newp[graph[i][x2]][nv[x1]] = 2;
            }
        }
        for(int x1 = 0;x1 < graph[i].size();x1++){
            for(int x2 = 0;x2 < graph[i].size();x2++){
                if(graph[i][x1] == graph[i][x2]) continue;
                if(newp[graph[i][x1]][graph[i][x2]]) continue;
                newp[graph[i][x1]][graph[i][x2]] = newp[graph[i][x2]][graph[i][x1]] = 2;
            }
        }
        b[nv[0]][nv.back()] = 1;
        b[nv.back()][nv[0]] = 1;
    }
    for(int i = 0;i < p.size();i++){
        for(int j = 0;j < p.size();j++){
            if(i == j) continue;
            if(p[i][j] != newp[i][j]) return 0;
        }
    }
    build(b);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'void dfs(int, int)':
supertrees.cpp:12:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i = 0;i < v[x].size();i++){
      |                   ~~^~~~~~~~~~~~~
supertrees.cpp: In function 'void make_tree(int)':
supertrees.cpp:20:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i = 0;i < v[x].size();i++){
      |                   ~~^~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:38:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int j = 0;j < p.size();j++){
      |                       ~~^~~~~~~~~~
supertrees.cpp:45:21: 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 i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:50:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i = 0;i < p.size();i++) visited[i] = false;
      |                   ~~^~~~~~~~~~
supertrees.cpp:53:25: 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 = 0;j < graph[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:58:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for(int x1 = 0;x1 < sametree.size();x1++){
      |                            ~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:59:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |                 for(int x2 = 0;x2 < sametree.size();x2++){
      |                                ~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:69:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int j = 0;j < nv.size() - 1;j++){
      |                       ~~^~~~~~~~~~~~~~~
supertrees.cpp:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int x1 = 0;x1 < nv.size();x1++){
      |                        ~~~^~~~~~~~~~~
supertrees.cpp:74:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             for(int x2 = 0;x2 < graph[i].size();x2++){
      |                            ~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:80:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int x1 = 0;x1 < graph[i].size();x1++){
      |                        ~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:81:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             for(int x2 = 0;x2 < graph[i].size();x2++){
      |                            ~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:90:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:91:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for(int j = 0;j < p.size();j++){
      |                       ~~^~~~~~~~~~

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