Submission #308982

#	Time	Username	Problem	Language	Result	Execution time	Memory
308982		tjdgus4384	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1 ms	384 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
vector<int> v[1001];
vector<int> graph[1001], trees[1001];
int group[1001], pa[1001];
bool visited[1001], visit[1001];

int find(int x){
    if(pa[x] == x) return x;
    return pa[x] = find(pa[x]);
}
void merge(int x, int y){
    x = find(x), y = find(y);
    if(x == y) return;
    pa[x] = y;
}

void dfs(int x, int cnt){
    if(visited[x]) return;
    visited[x] = true;
    group[x] = cnt;
    graph[cnt].push_back(x);
    for(int i = 0;i < v[x].size();i++){
        dfs(v[x][i], cnt);
    }
}

int construct(vector<vector<int> > p){
    for(int i = 0;i < p.size();i++){
        pa[i] = i;
        for(int j = 0;j < p[i].size();j++){
            if(i == j) continue;
            if(p[i][j]) v[i].push_back(j);
        }
        if(v[i].size() == 0) visit[i] = true;
    }
    int cnt = 0;
    for(int i = 0;i < p.size();i++){
        if(visited[i]) continue;
        dfs(i, cnt); cnt++;
    }
    for(int i = 0;i < cnt;i++){
        int maxchk = 0;
        bool chk[4] = {0, 0, 0, 0};
        for(int j = 0;j < graph[i].size();j++){
            int x = graph[i][j], maxi = 0;
            for(int k = 0;k < p.size();k++){
                if(x == k) continue;
                chk[p[x][k]] = true;
                maxi = max(maxi, p[x][k]);
                maxchk = max(maxchk, p[x][k]);
                if(p[x][k] && group[k] != group[x]) return 0;
                if(!p[x][k] && group[k] == group[x]) return 0;
            }
            if(maxi != maxchk) return 0;
        }
        if(chk[2] && chk[3]) return 0;
    }
    for(int i = 0;i < cnt;i++){
        for(int j = 0;j < graph[i].size();j++){
            int x = graph[i][j];
            for(int k = 0;k < v[x].size();k++){
                if(x == v[x][k]) continue;
                if(p[x][v[x][k]] == 1) merge(x, v[x][k]);
            }
        }
    }
    for(int i = 0;i < cnt;i++){
        for(int j = 0;j < graph[i].size();j++){
            int x = graph[i][j];
            for(int k = 0;k < v[x].size();k++){
                if(x == v[x][k]) continue;
                if(p[x][v[x][k]] != 1 && find(x) == find(v[x][k])) return 0;
            }
        }
    }
    for(int i = 0;i < p.size();i++) trees[find(i)].push_back(i);
    vector<vector<int> > b(p.size());
    for(int i = 0;i < p.size();i++) b[i].resize(p.size(), 0);
    for(int i = 0;i < p.size();i++){
        if(trees[i].size() <= 1) continue;
        for(int j = 0;j < trees[i].size() - 1;j++){
            b[trees[i][j]][trees[i][j+1]] = 1;
            b[trees[i][j+1]][trees[i][j]] = 1;
            if(trees[i][j] != i) visit[trees[i][j]] = true;
        }
        b[trees[i].back()][trees[i][0]] = 1;
        b[trees[i][0]][trees[i].back()] = 1;
    }

    for(int i = 0;i < p.size();i++) {pa[i] = i;trees[i].clear();}

    for(int i = 0;i < cnt;i++){
        for(int j = 0;j < graph[i].size();j++){
            int x = graph[i][j];
            if(visit[x]) continue;
            for(int k = 0;k < v[x].size();k++){
                if(x == v[x][k] || visit[v[x][k]]) continue;
                if(p[x][v[x][k]] == 2) merge(x, v[x][k]);
            }
        }
    }
    for(int i = 0;i < cnt;i++){
        for(int j = 0;j < graph[i].size();j++){
            int x = graph[i][j];
            if(visit[x]) continue;
            for(int k = 0;k < v[x].size();k++){
                if(x == v[x][k] || visit[v[x][k]]) continue;
                if(p[x][v[x][k]] != 2 && find(x) == find(v[x][k])) return 0;
            }
        }
    }
    for(int i = 0;i < p.size();i++){
        if(visit[i]) continue;
        trees[find(i)].push_back(i);
    }
    for(int i = 0;i < p.size();i++){
        if(trees[i].size() <= 1) continue;
        for(int j = 0;j < trees[i].size() - 1;j++){
            b[trees[i][j]][trees[i][j+1]] = 1;
            b[trees[i][j+1]][trees[i][j]] = 1;
            visit[trees[i][j]] = true;
        }
        visit[trees[i].back()] = true;
        b[trees[i].back()][trees[i][0]] = 1;
        b[trees[i][0]][trees[i].back()] = 1;
    }

    for(int i = 0;i < p.size();i++) {pa[i] = i;trees[i].clear();}

    for(int i = 0;i < cnt;i++){
        for(int j = 0;j < graph[i].size();j++){
            int x = graph[i][j];
            if(visit[x]) continue;
            for(int k = 0;k < v[x].size();k++){
                if(x == v[x][k] || visit[v[x][k]]) continue;
                if(p[x][v[x][k]] == 3) merge(x, v[x][k]);
            }
        }
    }
    for(int i = 0;i < cnt;i++){
        for(int j = 0;j < graph[i].size();j++){
            int x = graph[i][j];
            if(visit[x]) continue;
            for(int k = 0;k < v[x].size();k++){
                if(x == v[x][k] || visit[v[x][k]]) continue;
                if(p[x][v[x][k]] != 3 && find(x) == find(v[x][k])) return 0;
            }
        }
    }
    for(int i = 0;i < p.size();i++){
        if(visit[i]) continue;
        trees[find(i)].push_back(i);
    }
    for(int i = 0;i < p.size();i++){
        if(visit[i]) continue;
        if(trees[i].size() <= 1) continue;
        if(trees[i].size() <= 3) return 0;
        for(int j = 0;j < trees[i].size() - 1;j++){
            b[trees[i][j]][trees[i][j+1]] = 1;
            b[trees[i][j+1]][trees[i][j]] = 1;
        }
        b[trees[i].back()][trees[i][0]] = 1;
        b[trees[i][0]][trees[i].back()] = 1;
        b[trees[i][0]][trees[i][3]] = 1;
    }
    build(b);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'void dfs(int, int)':
supertrees.cpp:24:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i = 0;i < v[x].size();i++){
      |                   ~~^~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:30:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:32:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for(int j = 0;j < p[i].size();j++){
      |                       ~~^~~~~~~~~~~~~
supertrees.cpp:39:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:46:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int j = 0;j < graph[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:48:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             for(int k = 0;k < p.size();k++){
      |                           ~~^~~~~~~~~~
supertrees.cpp:61:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for(int j = 0;j < graph[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:63:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             for(int k = 0;k < v[x].size();k++){
      |                           ~~^~~~~~~~~~~~~
supertrees.cpp:70:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for(int j = 0;j < graph[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:72:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             for(int k = 0;k < v[x].size();k++){
      |                           ~~^~~~~~~~~~~~~
supertrees.cpp:78:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i = 0;i < p.size();i++) trees[find(i)].push_back(i);
      |                   ~~^~~~~~~~~~
supertrees.cpp:80:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i = 0;i < p.size();i++) b[i].resize(p.size(), 0);
      |                   ~~^~~~~~~~~~
supertrees.cpp:81:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:83:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for(int j = 0;j < trees[i].size() - 1;j++){
      |                       ~~^~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:92:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i = 0;i < p.size();i++) {pa[i] = i;trees[i].clear();}
      |                   ~~^~~~~~~~~~
supertrees.cpp:95:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(int j = 0;j < graph[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:98:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             for(int k = 0;k < v[x].size();k++){
      |                           ~~^~~~~~~~~~~~~
supertrees.cpp:105:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for(int j = 0;j < graph[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:108:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             for(int k = 0;k < v[x].size();k++){
      |                           ~~^~~~~~~~~~~~~
supertrees.cpp:114:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:118:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:120:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         for(int j = 0;j < trees[i].size() - 1;j++){
      |                       ~~^~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:130:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     for(int i = 0;i < p.size();i++) {pa[i] = i;trees[i].clear();}
      |                   ~~^~~~~~~~~~
supertrees.cpp:133:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         for(int j = 0;j < graph[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:136:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |             for(int k = 0;k < v[x].size();k++){
      |                           ~~^~~~~~~~~~~~~
supertrees.cpp:143:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |         for(int j = 0;j < graph[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:146:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |             for(int k = 0;k < v[x].size();k++){
      |                           ~~^~~~~~~~~~~~~
supertrees.cpp:152:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:156:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:160:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |         for(int j = 0;j < trees[i].size() - 1;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