Submission #308980

#	Time	Username	Problem	Language	Result	Execution time	Memory
308980		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(p[i][j]) v[i].push_back(j);
        }
    }
    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() <= 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:37:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:44:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int j = 0;j < graph[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:46:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             for(int k = 0;k < p.size();k++){
      |                           ~~^~~~~~~~~~
supertrees.cpp:59:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int j = 0;j < graph[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:61:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             for(int k = 0;k < v[x].size();k++){
      |                           ~~^~~~~~~~~~~~~
supertrees.cpp:68:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(int j = 0;j < graph[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:70:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             for(int k = 0;k < v[x].size();k++){
      |                           ~~^~~~~~~~~~~~~
supertrees.cpp:76:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i = 0;i < p.size();i++) trees[find(i)].push_back(i);
      |                   ~~^~~~~~~~~~
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++) b[i].resize(p.size(), 0);
      |                   ~~^~~~~~~~~~
supertrees.cpp:79:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:81:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for(int j = 0;j < trees[i].size() - 1;j++){
      |                       ~~^~~~~~~~~~~~~~~~~~~~~
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++) {pa[i] = i;trees[i].clear();}
      |                   ~~^~~~~~~~~~
supertrees.cpp:93:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for(int j = 0;j < graph[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:96:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             for(int k = 0;k < v[x].size();k++){
      |                           ~~^~~~~~~~~~~~~
supertrees.cpp:103:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int j = 0;j < graph[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:106:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |             for(int k = 0;k < v[x].size();k++){
      |                           ~~^~~~~~~~~~~~~
supertrees.cpp:112:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:116:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:118:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(int j = 0;j < trees[i].size() - 1;j++){
      |                       ~~^~~~~~~~~~~~~~~~~~~~~
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++) {pa[i] = i;trees[i].clear();}
      |                   ~~^~~~~~~~~~
supertrees.cpp:131:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         for(int j = 0;j < graph[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:134:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |             for(int k = 0;k < v[x].size();k++){
      |                           ~~^~~~~~~~~~~~~
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 < graph[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:144:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |             for(int k = 0;k < v[x].size();k++){
      |                           ~~^~~~~~~~~~~~~
supertrees.cpp:150:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:154:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |     for(int i = 0;i < p.size();i++){
      |                   ~~^~~~~~~~~~
supertrees.cpp:157:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |         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