oj.uz

Submission #366893

# Submission time Handle Problem Language Result Execution time Memory
366893 2021-02-15T16:22:42 Z rumen_m Connecting Supertrees (IOI20_supertrees) C++17
0 / 100
 1 ms 364 KB 
#include "supertrees.h"
#include <vector>
using namespace std;
const int maxn = 1005;
vector <int> g[maxn];
vector <int> ones[maxn];
int id[maxn], ids = 0;
bool vis[maxn];
vector <int> groups[maxn];
int ans[maxn][maxn];
int 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(row[j]==0&&id[i]==id[j])return 0;
            if(row[j]==1&&newids[i]!=newids[j])return 0;
        }

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

Compilation message

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Answer gives possible 0 while actual possible 1
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Answer gives possible 0 while actual possible 1
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Incorrect 0 ms 364 KB Answer gives possible 0 while actual possible 1
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Incorrect 0 ms 364 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Answer gives possible 0 while actual possible 1
4 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Answer gives possible 0 while actual possible 1
4 Halted 0 ms 0 KB -