Submission #366902

#	Time	Username	Problem	Language	Result	Execution time	Memory
366902		rumen_m	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	298 ms	34924 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3005;
vector <short> g[maxn];
vector <short> ones[maxn];
short id[maxn], ids = 0;
bool vis[maxn];
vector <int> groups[maxn];
short ans[maxn][maxn];
short newids[maxn];
void dfs(int v)
{
    id[v]=ids;
    int i;
    for(i=0;i<g[v].size();i++)
    {
        if(id[g[v][i]]==0)dfs(g[v][i]);
    }
}
void solve(int v)
{
    newids[v] = ids;
    vis[v] = 1;
    int i;
    for(i=0;i<ones[v].size();i++)
    {
        if(!vis[ones[v][i]])
        {
            ans[v][ones[v][i]] = 1;
            solve(ones[v][i]);
        }
    }
}
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	int i,j,t;
	for(i=0;i<n;i++)
        for(j=0;j<n;j++)
    {
        if(i==j)continue;
        if(p[i][j]==3)return 0;
        if(p[i][j]>0)
        {
           /* for(t=0;t<n;t++)
            {
                 if((p[i][t]>0)^(p[j][t]>0)==1)return 0;
                 if(p[i][j]==1)
                    if(p[i][t]==1^p[j][t]==1)return 0;
            }*/

        }
        if(p[i][j]!=0)
        {
            g[i].push_back(j);
            g[j].push_back(i);
        }
        if(p[i][j]==1)
        {
            ones[i].push_back(j);
            ones[j].push_back(i);
        }
    }
    for(i=0;i<n;i++)
    {
        if(id[i]==0){ids++;dfs(i);}
    }
    for(i=0;i<n;i++)
    {
        if(!vis[i])
        {
            groups[id[i]].push_back(i);
            ids++;
            solve(i);
        }
    }
    for(i=1;i<=ids;i++)
    {
        if(groups[i].size()==2)return 0;
        if(groups[i].size()<=2)continue;
        ans[groups[i][0]][groups[i][groups[i].size()-1]] = 1;
        for(j=1;j<groups[i].size();j++)
        {
            ans[groups[i][j-1]][groups[i][j]] = 1;
        }
    }
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		for(j=0;j<n;j++)
        {
            row[j] = ans[i][j]|ans[j][i];
            if(i==j)continue;
            if(p[i][j]==0&&id[i]==id[j]){return 0;}
            if(p[i][j]==1&&newids[i]!=newids[j])return 0;
        }

		answer.push_back(row);
	}
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'void dfs(int)':
supertrees.cpp:17:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(i=0;i<g[v].size();i++)
      |             ~^~~~~~~~~~~~
supertrees.cpp: In function 'void solve(int)':
supertrees.cpp:27:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(i=0;i<ones[v].size();i++)
      |             ~^~~~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for(j=1;j<groups[i].size();j++)
      |                 ~^~~~~~~~~~~~~~~~~
supertrees.cpp:38:10: warning: unused variable 't' [-Wunused-variable]
   38 |  int i,j,t;
      |          ^

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