Submission #308985

#	Time	Username	Problem	Language	Result	Execution time	Memory
308985		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];
            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]] == 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];
            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]] != 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++){
        bool b = true;
        for(int j = 0;j < v[i].size();j++){
            if(visit[v[i][j]]) continue;
            if(p[i][j]) b = false;
        }
        if(b) visit[i] = true;
    }

    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++){
        bool b = true;
        for(int j = 0;j < v[i].size();j++){
            if(visit[v[i][j]]) continue;
            if(p[i][j]) b = false;
        }
        if(b) visit[i] = true;
    }

    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][2]] = 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:64:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             for(int k = 0;k < v[x].size();k++){
      |                           ~~^~~~~~~~~~~~~
supertrees.cpp:71:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int j = 0;j < graph[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:74:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             for(int k = 0;k < v[x].size();k++){
      |                           ~~^~~~~~~~~~~~~
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++) trees[find(i)].push_back(i);
      |                   ~~^~~~~~~~~~
supertrees.cpp:82:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i = 0;i < p.size();i++) b[i].resize(p.size(), 0);
      |                   ~~^~~~~~~~~~
supertrees.cpp:83:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:85:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(int j = 0;j < trees[i].size() - 1;j++){
      |                       ~~^~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
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 < v[i].size();j++){
      |                       ~~^~~~~~~~~~~~~
supertrees.cpp:102:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i = 0;i < p.size();i++) {pa[i] = i;trees[i].clear();}
      |                   ~~^~~~~~~~~~
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:115:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for(int j = 0;j < graph[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:118:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |             for(int k = 0;k < v[x].size();k++){
      |                           ~~^~~~~~~~~~~~~
supertrees.cpp:124:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:128:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:130:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         for(int j = 0;j < trees[i].size() - 1;j++){
      |                       ~~^~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:139:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:141:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |         for(int j = 0;j < v[i].size();j++){
      |                       ~~^~~~~~~~~~~~~
supertrees.cpp:148:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |     for(int i = 0;i < p.size();i++) {pa[i] = i;trees[i].clear();}
      |                   ~~^~~~~~~~~~
supertrees.cpp:151:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |         for(int j = 0;j < graph[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:154:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |             for(int k = 0;k < v[x].size();k++){
      |                           ~~^~~~~~~~~~~~~
supertrees.cpp:161:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |         for(int j = 0;j < graph[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:164:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |             for(int k = 0;k < v[x].size();k++){
      |                           ~~^~~~~~~~~~~~~
supertrees.cpp:170:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:174:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:178:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |         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