Submission #595303

#	Time	Username	Problem	Language	Result	Execution time	Memory
595303		Red_Inside	Connecting Supertrees (IOI20_supertrees)	C++17	96 / 100	171 ms	24016 KiB

supertrees

#include "supertrees.h"


#include <bits/stdc++.h>

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long

using namespace std;
const int maxn=1e6+10,LOG=17,mod=998244353;
int block = 226, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define bt(i) (1 << (i))
//#define int ll
const int inf=2e9;
#define y1 yy
#define prev pre
#define pii pair <int, int>

int used[maxn], good[maxn], root[maxn];

int construct(vector <vector <int> > a)
{
	int n = a[0].size();
	vector <vector <int> > ans;
	ans = a;
	forn(0, i, n-1) forn(0, j, n-1) ans[i][j] = 0;
	vector <int> roots;
	forn(0, i, n-1)
	{
		if(a[i][i] != 1) return 0;
		if(used[i]) continue;
		vector <int> vec;
		forn(0, j, n-1)
		{
			if(a[i][j] == 1) 
			{
				vec.pb(j);
				used[j] = 1;
			}
		}
		FOR(0, j, vec.size())
		{
			forn(0, k, n-1)
			{
				if(a[i][k] == 1 && a[vec[j]][k] != 1) return 0;
				if(a[i][k] != 1 && a[vec[j]][k] == 1) return 0;
			}
		}
		FOR(1, j, vec.size())
		{
			ans[vec[j]][vec[j-1]] = 1;
			ans[vec[j-1]][vec[j]] = 1;
		}
//		cout << "NEW TREE: ";
//		for(auto j : vec) cout << j << " ";
//		cout << endl;
		for(auto j : vec) root[j] = vec[0];
		roots.pb(vec[0]);
	}
	forn(0, i, n-1) used[i] = 0;
	FOR(0, i, roots.size())
	{
		if(used[i]) continue;
		vector <int> vec;
		FOR(0, j, roots.size())
		{
			if(a[roots[i]][roots[j]] == 2)
			{
				used[j] = i + 1;
				vec.pb(roots[j]);
			}
		}
		vec.pb(roots[i]);
		if(vec.size() == 2) return 0;
		if(vec.size() == 1) continue;
		FOR(0, j, vec.size())
		{
			FOR(j + 1, k, vec.size())
			{
				if(a[vec[j]][vec[k]] != 2) return 0;
			}
		}
		FOR(0, j, vec.size())
		{
			forn(0, k, n-1)
			{
//				cout << vec[j] << ' ' << k << " " << root[k] << " " << roots[i] << endl;
				if(a[vec[j]][k] == 2 && root[k] != roots[i] && a[roots[i]][root[k]] != 2) return 0;
				if(a[vec[j]][k] == 0 && a[roots[i]][root[k]] != 0) return 0;
			}
		}
		FOR(1, j, vec.size())
		{
			ans[vec[j]][vec[j-1]] = 1;
			ans[vec[j-1]][vec[j]] = 1;
		}
		ans[vec[0]][vec.back()] = 1;
		ans[vec.back()][vec[0]] = 1;
	}
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:12:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
   55 |   FOR(0, j, vec.size())
      |          ~~~~~~~~~~~~~                 
supertrees.cpp:55:3: note: in expansion of macro 'FOR'
   55 |   FOR(0, j, vec.size())
      |   ^~~
supertrees.cpp:12:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
   63 |   FOR(1, j, vec.size())
      |          ~~~~~~~~~~~~~                 
supertrees.cpp:63:3: note: in expansion of macro 'FOR'
   63 |   FOR(1, j, vec.size())
      |   ^~~
supertrees.cpp:12:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
   75 |  FOR(0, i, roots.size())
      |         ~~~~~~~~~~~~~~~                
supertrees.cpp:75:2: note: in expansion of macro 'FOR'
   75 |  FOR(0, i, roots.size())
      |  ^~~
supertrees.cpp:12:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
   79 |   FOR(0, j, roots.size())
      |          ~~~~~~~~~~~~~~~               
supertrees.cpp:79:3: note: in expansion of macro 'FOR'
   79 |   FOR(0, j, roots.size())
      |   ^~~
supertrees.cpp:12:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
   90 |   FOR(0, j, vec.size())
      |          ~~~~~~~~~~~~~                 
supertrees.cpp:90:3: note: in expansion of macro 'FOR'
   90 |   FOR(0, j, vec.size())
      |   ^~~
supertrees.cpp:12:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
   92 |    FOR(j + 1, k, vec.size())
      |               ~~~~~~~~~~~~~            
supertrees.cpp:92:4: note: in expansion of macro 'FOR'
   92 |    FOR(j + 1, k, vec.size())
      |    ^~~
supertrees.cpp:12:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
   97 |   FOR(0, j, vec.size())
      |          ~~~~~~~~~~~~~                 
supertrees.cpp:97:3: note: in expansion of macro 'FOR'
   97 |   FOR(0, j, vec.size())
      |   ^~~
supertrees.cpp:12:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
  106 |   FOR(1, j, vec.size())
      |          ~~~~~~~~~~~~~                 
supertrees.cpp:106:3: note: in expansion of macro 'FOR'
  106 |   FOR(1, j, vec.size())
      |   ^~~

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