oj.uz

답안 #1099904

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1099904 2024-10-12T05:48:39 Z model_code 스핑크스 (IOI24_sphinx) C++17
3 / 100
 72 ms 728 KB 
// incorrect/bakry_protocol_violation.cpp

//#include "grader.cpp"
#include "sphinx.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX = 250 + 10;

int n, m;
vector< vector<int> >adj(MAX);

int vis[MAX];

void dfs(int node)
{
	vis[node] = 1;
	for(auto &child : adj[node])
	{
		if(vis[child])
			continue;
		dfs(child);
	}
}

int countComps(int node)
{
	vector<int>v;
	for(int i = 0; i <= node; ++i)
		v.push_back(-1);
	for(int i = node+1; i < n; ++i)
		v.push_back(n);
	int comps = perform_experiment(v);
	memset(vis, 0, sizeof(vis));
	for(int i = 0; i <= node; ++i)
		vis[i] = 1;
	int nComps = 0;
	for(int i = 0; i < n; ++i)
	{
		if(vis[i])
			continue;
		nComps++;
		dfs(i);
	}
	return (comps - nComps);
}

bool check(int node, int l, int r, vector< vector<int> >&CCs)
{
	vector<int>v;
	for(int i = 0; i < n; ++i)
		v.push_back(n);
	v[node] = -1;
	for(int i = l; i <= r; ++i)
	{
		for(auto &j : CCs[i])
			v[j] = -1;
	}
	int comps = perform_experiment(v);
	memset(vis, 0, sizeof(vis));
	vis[node] = 1;
	for(int i = l; i <= r; ++i)
	{
		for(auto &j : CCs[i])
			vis[j] = 1;
	}
	int nComps = r-l+1 + 1;
	for(int i = 0; i < n; ++i)
	{
		if(vis[i])
			continue;
		nComps++;
		dfs(i);
	}
	return (comps < nComps);
}

int mark[MAX], cmp[MAX];

vector< vector<int> >findCCs()
{
	vector< vector<int> >CCs, CCs2;
	vector<int>neigbours;
	CCs.push_back({0});
	int compCnt = 1;
	for(int i = 1; i < n; ++i)
	{
		neigbours.clear(), CCs2.clear();
		memset(mark, 0, sizeof(mark));
		int x = countComps(i);
		int neigbourCnt = compCnt+1 - x;
		int last = -1;
		for(int j = 0; j < neigbourCnt; ++j)
		{
			int l = last+1, r = CCs.size() - 1;
			int idx = r;
			while(l <= r)
			{
				int mid = (l + r) >> 1 ;
				if(check(i, l, mid, CCs))
					idx = mid, r = mid-1;
				else
					l = mid+1;
			}
			mark[idx] = 1;
			neigbours.push_back(idx);
			last = idx;
		}
		compCnt = x;
		for(int i = 0; i < CCs.size(); ++i)
		{
			if(mark[i])
				continue;
			CCs2.push_back(CCs[i]);
		}
		CCs2.push_back({i});
		for(auto &i : neigbours)
		{
			for(auto &node : CCs[i])
				CCs2.back().push_back(node);
		}
		CCs = CCs2;
		compCnt = CCs.size();
	}
	for(int i = 0; i < CCs.size(); ++i)
	{
		for(auto &node : CCs[i])
			cmp[node] = i;
	}
	return CCs;
}

vector< vector<int> >CCs;

vector< vector<int> >decomposeGraph()
{
	memset(mark, -1, sizeof(mark));
	int m = CCs.size();
	vector< vector<int> >decomposedAdj(m);
	for(int i = 0; i < m; ++i)
	{
		for(auto &node : CCs[i])
		{
			for(auto &child : adj[node])
			{
				int x = cmp[child];
				if(mark[x] == i)
					continue;
				decomposedAdj[i].push_back(x);
				mark[x] = i;
			}
		}
	} 
	return decomposedAdj;
}

vector< vector<int> >decomposedAdj, stAdj;

void dfs2(int node)
{
	vis[node] = 1;
	for(auto &child : decomposedAdj[node])
	{
		if(vis[child])
			continue;
		stAdj[node].push_back(child), stAdj[child].push_back(node);
		dfs2(child);
	}
}

void findST()
{
	memset(vis, 0, sizeof(vis));
	int m = CCs.size();
	stAdj = vector< vector<int> >(m+5);
	for(int i = 0; i < m; ++i)
	{
		if(vis[i])
			continue;
		dfs2(i);
	}
}

vector<int>s[2];

void findTwoSets(int node, int par, int col)
{
	s[col].push_back(node);
	for(auto &child : stAdj[node])
	{
		if(child == par)
			continue;
		findTwoSets(child, node, !col);
	}
}

void dfs3(int node, vector<int>&v)
{
	vis[node] = 1;
	for(auto &child : decomposedAdj[node])
	{
		if(vis[child] || v[child] != v[node])
			continue;
		dfs3(child, v);
	}
}

int countCompressedComps(int ty, int l, int r, int col, vector<int>&v)
{
	memset(vis, 0, sizeof(vis));
	for(int i = l; i <= r; ++i)
		vis[s[ty][i]] = 1;
	int cnt = 0;
	for(int i = 0; i < CCs.size(); ++i)
	{
		if(vis[i])
			continue;
		cnt++;
		dfs3(i, v);
	}
	return cnt;
}

bool check(int ty, int l, int r, int col)
{
	vector<int>v(n), v2(n);
	for(int i = 0; i < l; ++i)
	{
		v2[s[ty][i]] = n;
		for(auto &x : CCs[s[ty][i]])
			v[x] = n;
	}
	for(int i = l; i <= r; ++i)
	{
		v2[s[ty][i]] = -1;
		for(auto &x : CCs[s[ty][i]])
			v[x] = -1;
	}
	for(int i = r+1; i < s[ty].size(); ++i)
	{
		v2[s[ty][i]] = n;
		for(auto &x : CCs[s[ty][i]])
			v[x] = n;
	}
	for(auto &i : s[!ty])
	{
		v2[i] = col;
		for(auto &x : CCs[i])
			v[x] = col;
	}
	int comps = perform_experiment(v);
	return (comps < countCompressedComps(ty, l, r, col, v2) + r-l+1);
}

void solve(int col, int ty, int st, vector<int>&ans)
{
	if(st == s[ty].size())
		return;
	vector<int>v(n);
	for(int i = 0; i < st; ++i)
	{
		for(auto &node : CCs[s[ty][i]])
			v[node] = n;
	}
	for(int i = st; i < s[ty].size(); ++i)
	{
		for(auto &node : CCs[s[ty][i]])
			v[node] = -1;
	}
	for(auto &i : s[!ty])
	{
		for(auto &node : CCs[i])
			v[node] = col;
	}
	int comps = perform_experiment(v);
	if(comps == countCompressedComps(ty, st, s[ty].size()-1, col, v) + s[ty].size() - st)
		return;
	int l = st, r = s[ty].size() - 1;
	int idx = r;
	while(l <= r)
	{
		int mid = (l + r) >> 1;
		if(check(ty, st, mid, col))
			idx = mid, r = mid-1;
		else
			l = mid+1;
	}
	for(auto &node : CCs[s[ty][idx]])
		ans[node] = col;
	solve(col, ty, idx+1, ans);
}

vector<int>handleOneComp()
{
	vector<int>ans(n);
	for(int c = 0; c < n; ++c)
	{
		vector<int>v(n);
		v[0] = -1;
		for(int i = 1; i < n; ++i)
			v[i] = c;
		int compCnt = perform_experiment(v);
		if(compCnt == 1)
		{
			for(int i = 0; i < n; ++i)
				ans[i] = c;
			break;
		}
	}
	return ans;
}

vector<int>findColors()
{
	vector<int>ans(n, 0);
	for(int i = 0; i < n; ++i)
		solve(i, 0, 0, ans), solve(i, 1, 0, ans);
	return ans;
}

std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) 
{
	n = N, m = X.size();
	for(int i = 0; i < m; ++i)
		adj[X[i]].push_back(Y[i]);
	CCs = findCCs();
	if(CCs.size() == 1)
		return handleOneComp();
	decomposedAdj = decomposeGraph();
	findST();
	findTwoSets(0, -1, 0);
	return findColors();
}

Compilation message

sphinx.cpp: In function 'std::vector<std::vector<int> > findCCs()':
sphinx.cpp:111:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   for(int i = 0; i < CCs.size(); ++i)
      |                  ~~^~~~~~~~~~~~
sphinx.cpp:126:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |  for(int i = 0; i < CCs.size(); ++i)
      |                 ~~^~~~~~~~~~~~
sphinx.cpp: In function 'int countCompressedComps(int, int, int, int, std::vector<int>&)':
sphinx.cpp:215:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |  for(int i = 0; i < CCs.size(); ++i)
      |                 ~~^~~~~~~~~~~~
sphinx.cpp: In function 'bool check(int, int, int, int)':
sphinx.cpp:240:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  240 |  for(int i = r+1; i < s[ty].size(); ++i)
      |                   ~~^~~~~~~~~~~~~~
sphinx.cpp: In function 'void solve(int, int, int, std::vector<int>&)':
sphinx.cpp:258:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  258 |  if(st == s[ty].size())
      |     ~~~^~~~~~~~~~~~~~~
sphinx.cpp:266:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  266 |  for(int i = st; i < s[ty].size(); ++i)
      |                  ~~^~~~~~~~~~~~~~
sphinx.cpp:277:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  277 |  if(comps == countCompressedComps(ty, st, s[ty].size()-1, col, v) + s[ty].size() - st)
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB #experiments: 17

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB #experiments: 3
2 Correct 0 ms 344 KB #experiments: 7
3 Correct 0 ms 344 KB #experiments: 7
4 Correct 0 ms 344 KB #experiments: 4

Subtask #2
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB #experiments: 17
2 Correct 0 ms 344 KB #experiments: 3
3 Correct 0 ms 344 KB #experiments: 7
4 Correct 0 ms 344 KB #experiments: 7
5 Correct 0 ms 344 KB #experiments: 4
6 Correct 2 ms 344 KB #experiments: 123
7 Partially correct 2 ms 448 KB Partially correct
8 Partially correct 3 ms 344 KB Partially correct
9 Partially correct 3 ms 344 KB Partially correct
10 Partially correct 3 ms 344 KB Partially correct
11 Partially correct 4 ms 344 KB Partially correct
12 Partially correct 7 ms 344 KB Partially correct
13 Correct 6 ms 344 KB #experiments: 435
14 Correct 1 ms 344 KB #experiments: 113
15 Partially correct 3 ms 344 KB Partially correct
16 Partially correct 6 ms 344 KB Partially correct
17 Incorrect 5 ms 480 KB Vertices 0 and 2 do not have the same color, but they do in returned answer
18 Halted 0 ms 0 KB -

Subtask #3
0.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB #experiments: 3
2 Correct 0 ms 344 KB #experiments: 7
3 Correct 0 ms 344 KB #experiments: 7
4 Correct 0 ms 344 KB #experiments: 4
5 Correct 2 ms 344 KB #experiments: 123
6 Partially correct 2 ms 448 KB Partially correct
7 Partially correct 3 ms 344 KB Partially correct
8 Partially correct 3 ms 344 KB Partially correct
9 Partially correct 3 ms 344 KB Partially correct
10 Partially correct 4 ms 344 KB Partially correct
11 Partially correct 7 ms 344 KB Partially correct
12 Correct 6 ms 344 KB #experiments: 435
13 Correct 22 ms 484 KB #experiments: 1101
14 Partially correct 25 ms 480 KB Partially correct
15 Partially correct 38 ms 704 KB Partially correct
16 Partially correct 42 ms 464 KB Partially correct
17 Partially correct 47 ms 476 KB Partially correct
18 Partially correct 59 ms 728 KB Partially correct
19 Incorrect 72 ms 512 KB #experiments reached 2751
20 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB #experiments: 3
2 Correct 0 ms 344 KB #experiments: 7
3 Correct 0 ms 344 KB #experiments: 7
4 Correct 0 ms 344 KB #experiments: 4
5 Correct 1 ms 344 KB #experiments: 113
6 Partially correct 3 ms 344 KB Partially correct
7 Partially correct 6 ms 344 KB Partially correct
8 Incorrect 5 ms 480 KB Vertices 0 and 2 do not have the same color, but they do in returned answer
9 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB #experiments: 17
2 Correct 0 ms 344 KB #experiments: 3
3 Correct 0 ms 344 KB #experiments: 7
4 Correct 0 ms 344 KB #experiments: 7
5 Correct 0 ms 344 KB #experiments: 4
6 Correct 2 ms 344 KB #experiments: 123
7 Partially correct 2 ms 448 KB Partially correct
8 Partially correct 3 ms 344 KB Partially correct
9 Partially correct 3 ms 344 KB Partially correct
10 Partially correct 3 ms 344 KB Partially correct
11 Partially correct 4 ms 344 KB Partially correct
12 Partially correct 7 ms 344 KB Partially correct
13 Correct 6 ms 344 KB #experiments: 435
14 Correct 1 ms 344 KB #experiments: 113
15 Partially correct 3 ms 344 KB Partially correct
16 Partially correct 6 ms 344 KB Partially correct
17 Incorrect 5 ms 480 KB Vertices 0 and 2 do not have the same color, but they do in returned answer
18 Halted 0 ms 0 KB -