oj.uz

Submission #464225

# Submission time Handle Problem Language Result Execution time Memory
464225 2021-08-12T14:41:16 Z koioi.org-dennisstar Chameleon's Love (JOI20_chameleon) C++17
0 / 100
 0 ms 200 KB 
#include "chameleon.h"
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> adj;
vector<int> bi[2];

void f(int b, int x, int s, int e) {
	if (s==e) {
		adj[x].emplace_back(bi[b][s]);
		adj[bi[b][s]].emplace_back(x);
		return ;
	}
	vector<int> v;
	v.emplace_back(x);
	int m=(s+e)/2;
	for (int i=s; i<=m; i++) v.emplace_back(bi[b][i]);
	if (Query(v)<v.size()) f(b, x, s, m);
	v.resize(1, x);
	for (int i=m+1; i<=e; i++) v.emplace_back(bi[b][i]);
	if (Query(v)<v.size()) f(b, x, m+1, e);
}

vector<int> vis; int vc;

void dfs(int i, int b) {
	vis[i]=vc;
	bi[b].emplace_back(i);
	for (auto &j:adj[i]) if (vis[j]!=vc) dfs(j, 1-b);
}

void div(int n) {
	bi[0].clear();
	bi[1].clear();
	vc++;
	for (int i=1; i<=n; i++) if (vis[i]!=vc) dfs(i, 0);
}

void Solve(int n) {
	adj.resize(2*n+1);
	vis.resize(2*n+1);
	for (int i=1; i<=2*n; i++) {
		for (int j=0; j<2; j++) if (bi[j].size()) f(j, i, 0, bi[j].size()-1);
		div(i);
	}

	auto chk = [&](int x, int y) {
		if (adj[x].size()==1||adj[y].size()==1) return true;
		int f1=0, f2=0;
		vector<int> v(3);
		v[0]=x, v[1]=y;
		for (auto &i:adj[x]) if (i!=y) {
			v[2]=i;
			if (Query(v)==1) { f1=1; break; }
		}
		for (auto &i:adj[y]) if (i!=x) {
			v[2]=i;
			if (Query(v)==1) { f2=1; break; }
		}
		return f1&&f2;
	};
	for (int i=1; i<=2*n; i++) for (auto &j:adj[i]) if (i<j&&chk(i, j)) {
		Answer(i, j);
		adj[j].clear();
		break;
	}
}

Compilation message

chameleon.cpp: In function 'void f(int, int, int, int)':
chameleon.cpp:19:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  if (Query(v)<v.size()) f(b, x, s, m);
      |      ~~~~~~~~^~~~~~~~~
chameleon.cpp:22:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  if (Query(v)<v.size()) f(b, x, m+1, e);
      |      ~~~~~~~~^~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 200 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 200 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 200 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 200 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 200 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -