oj.uz

Submission #432345

# Submission time Handle Problem Language Result Execution time Memory
432345 2021-06-18T08:23:40 Z arayi Connecting Supertrees (IOI20_supertrees) C++17
0 / 100
 1000 ms 23884 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
#define ad push_back
using namespace std;

const int N = 1111;
int col[N], sm[N], i1 = 1;
vector <vector <int> > b;
int n;
void dfs(int v)
{
	col[v] = 2;
	sm[v]++;
	for (int i = 0; i < n; i++)
	{
		if(col[i] != 2 && b[v][i]) dfs(i);
	}
	col[v] = 1;
}
int construct(std::vector<std::vector<int>> p) {
	n = p.size();
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if(p[i][j] > 3) return 0;
	for (int i = 0; i < n; i++)
	{
		if(sm[i])
		{
			for (int j = 0; j < n; j++)
			{
				if(p[i][j] && sm[i] != sm[j]) return 0;
				if(p[i][j] == 0 && sm[i] == sm[j]) return 0;
			}
		}
		else
		{
			for (int j = 0; j < n; j++)
			{
				if(p[i][j] && sm[j]) return 0;
				if(p[i][j]) sm[j] = i1;
			}
		}
		i1++;
	}
	b.resize(n);
	for (int i = 0; i < n; i++) b[i].resize(n);
	for (int i = 1; i < i1; i++)
	{
		vector<int> fp;
		for (int j = 0; j < n; j++)
			if(sm[j] == i) fp.ad(j);
		int nx = -1;
		for (int j = 0; j < fp.size(); j++)
		{
			if(col[fp[j]]) continue;
			if(nx != -1) b[nx][fp[j]] = b[fp[j]][nx] = 1;
			nx = fp[j];
			col[fp[j]] = 1;
			for (int k = j + 1; k < fp.size(); k++)
				if(p[fp[j]][fp[k]] == 1) b[fp[j]][fp[k]] = b[fp[k]][fp[j]] = 1, col[fp[k]] = 1;
		}		
		if(nx != -1 && nx != fp[0]) b[nx][fp[0]] = b[fp[0]][nx] = 1;
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++) sm[j] = col[j] = 0;
		dfs(i);
		for (int j = 0; j < n; j++) if(sm[j] != p[i][j]) return 0;
	}
	build(b);
	return 1;
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:53:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for (int j = 0; j < fp.size(); j++)
      |                   ~~^~~~~~~~~~~
supertrees.cpp:59:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    for (int k = j + 1; k < fp.size(); k++)
      |                        ~~^~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 21 ms 1124 KB Output is correct
7 Execution timed out 1088 ms 12032 KB Time limit exceeded

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 21 ms 1124 KB Output is correct
7 Execution timed out 1088 ms 12032 KB Time limit exceeded

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 296 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 10 ms 1212 KB Output is correct
9 Correct 240 ms 23884 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 31 ms 1228 KB Output is correct
13 Execution timed out 1081 ms 14068 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 63 ms 5756 KB Output is correct
5 Correct 402 ms 22020 KB Output is correct
6 Correct 246 ms 21988 KB Output is correct
7 Correct 866 ms 21996 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 72 ms 5760 KB Output is correct
10 Correct 558 ms 22016 KB Output is correct
11 Correct 268 ms 22012 KB Output is correct
12 Execution timed out 1091 ms 12136 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 21 ms 1124 KB Output is correct
7 Execution timed out 1088 ms 12032 KB Time limit exceeded

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 21 ms 1124 KB Output is correct
7 Execution timed out 1088 ms 12032 KB Time limit exceeded