제출 #977352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
977352		thegamercoder19	슈퍼트리 잇기 (IOI20_supertrees)	C++14	100 / 100	171 ms	28412 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

#define M_PI       3.14159265358979323846
#define FILER 0
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const ll MOD = pow(10, 9) + 7;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
const ull INFUL = 0x3f3f3f3f3f3f3f3f;
const ll INFT = 0x3f3f3f3f;
const ull MAX = 1LL << 24;
const ll MODD = 998244353;
const double EPS = 1e-10;
#define V vector
#define pll pair<ll, ll>
#define pull2 pair<ull,ull>
#define MS multiset
#define M map
#define Q queue
#define PQ priority_queue
#define IOF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define FOR(typ,i,a,b,c) for(typ i = a; i < b; i += c)
#define FORR(typ,i,a,b,c) for(typ i = a; i > b; i -= c)
#define FORA(a,i) for(auto &i : a)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define sorta(a) sort(all(a))
#define sortd(a) sort(all(a), greater<ll>())
#define setp(x) setprecision(x)<<fixed
#define RET return
#define log(a,b) log(b)/log(a)
#define WH(s) while(s)
#define WHI(t) WH(t--)
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define Yes cout<<"Yes"<<endl;
#define No cout<<"No"<<endl;
#define YESNO(s) cout << (s ? "YES" : "NO") << endl;
#define YesNo(s) cout<<(s?"Yes":"No")<<endl;
#define TYP 0
using namespace std;

struct dsu
{
	V<ll> p, rnk;
	ll n;
	dsu(ll sz) :n(sz)
	{
		p.assign(n, 0);
		iota(all(p), 0);
		rnk.assign(n, 0);
	}
	void clear()
	{
		p.assign(n, 0);
		iota(all(p), 0);
		rnk.assign(n, 0);
	}
	ll find(ll u) { RET u == p[u] ? u : p[u] = find(p[u]); }
	bool unite(ll u, ll v)
	{
		u = find(u), v = find(v);
		if (u == v)RET 0;
		if (rnk[u] < rnk[v]) swap(u, v);
		p[v] = u, rnk[u]++;
		RET 1;
	}
};
ll n;
V<V<int>> p1, g, ans, g1;
V<int> chk2;
V<bool> us;
void dfs(ll u, ll p)
{
	p1[u][p]++;
	us[u] = 1;
	FORA(g[u], v)
		if (!us[v])dfs(v, p);
	us[u] = 0;
}
int construct(std::vector<std::vector<int>> p)
{
	n = p.size();
	p1.resize(n, V<int>(n)); ans.resize(n, V<int>(n)); g.resize(n);
	us.resize(n);
	FOR(ll, i, 0, n, 1)
		FOR(ll, j, 0, n, 1)
		if (p[i][j] == 3) RET 0;
	dsu dsu(n);
	g1.assign(n, {});
	FOR(ll, i, 0, n, 1)
		FOR(ll, j, 0, n, 1)
		if (p[i][j] == 1) dsu.unite(i, j);
	FOR(ll, i, 0, n, 1) g1[dsu.find(i)].push_back(i);
	FOR(ll, i, 0, n, 1)
	{
		if (g1[i].empty()) continue;
	    chk2.push_back(i);
		ll sz = (g1[i].size() - 1);
		FOR(ll, j, 0, sz, 1)
			g[g1[i][j]].push_back(g1[i][j + 1]), g[g1[i][j + 1]].push_back(g1[i][j]), ans[g1[i][j]][g1[i][j + 1]] = ans[g1[i][j + 1]][g1[i][j]] = 1;
	}
	g1.assign(n, {});
	dsu.clear();
	FORA(chk2, u)
		FORA(chk2, v)
		if (p[u][v] == 2)dsu.unite(u, v);
	FOR(ll, i, 0, n, 1) g1[dsu.find(i)].push_back(i);
	FOR(ll, i, 0, n, 1)
	{
		//can't create cycle with 2 nodes
		if (g1[i].size() <= 2)continue;
		FOR(ll, j, 0, g1[i].size() - 1, 1)
			g[g1[i][j]].push_back(g1[i][j + 1]), g[g1[i][j + 1]].push_back(g1[i][j]), ans[g1[i][j]][g1[i][j + 1]] = ans[g1[i][j + 1]][g1[i][j]] = 1;
		g[g1[i].back()].push_back(g1[i][0]), g[g1[i][0]].push_back(g1[i].back());
		ans[g1[i].back()][g1[i][0]] = ans[g1[i][0]][g1[i].back()] = 1;
	}
	FOR(ll, u, 0, n, 1)
		dfs(u, u);
	FOR(ll, i, 0, n, 1)FOR(ll, j, 0, n, 1)if (p1[i][j] != p[i][j])RET 0;
	build(ans);
	RET 1;
	
}

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:24:43: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 | #define FOR(typ,i,a,b,c) for(typ i = a; i < b; i += c)
......
  115 |   FOR(ll, j, 0, g1[i].size() - 1, 1)
      |           ~~~~~~~~~~~~~~~~~~~~~~           
supertrees.cpp:115:3: note: in expansion of macro 'FOR'
  115 |   FOR(ll, j, 0, g1[i].size() - 1, 1)
      |   ^~~

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