답안 #68862 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68862	2018-08-18T20:21:13 Z	IvanC	도서관 (JOI18_library)	C++17	100 / 100	337 ms	856 KB

library

#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

const int MAXN = 1001;

static int pai[MAXN],v1[MAXN],v2[MAXN],N;
static vector<int> grafo[MAXN],temporario[MAXN],filhos[MAXN],M;

static void addEdge(int a,int b){
	grafo[a].push_back(b);
	grafo[b].push_back(a);
}

static int isAdj(int a,int b){

	M.clear();
	M.assign(N,0);

	M[a-1] = 1;
	M[b-1] = 1;

	int ans = Query(M);
	return (ans == 1);

}

static int find(int x){
	if(x == pai[x]) return x;
	return pai[x] = find(pai[x]);
}

static void join_case1(int x,int i){

	pai[i] = x;

	if(isAdj(v1[x],i)){
		addEdge(v1[x],i);
		v1[x] = i;
	}
	else{
		addEdge(v2[x],i);
		v2[x] = i;
	}

	filhos[x].push_back(i);

}

static void join_case2(int x,int y,int i){

	if(x > y) swap(x,y);

	int adj_v1x = isAdj(v1[x],i);
	int adj_v2x = 1 - adj_v1x;
	int adj_v1y = isAdj(v1[y],i);
	int adj_v2y = 1 - adj_v1y;

	if(adj_v1x) addEdge(v1[x],i);
	else addEdge(v2[x],i);
	if(adj_v1y) addEdge(v1[y],i);
	else addEdge(v2[y],i);

	if(adj_v1x == 1 && adj_v1y == 1){
		v1[x] = v2[y];

	}
	else if(adj_v1x == 1 && adj_v1y == 0){
		v1[x] = v1[y];
	}
	else if(adj_v1x == 0 && adj_v1y == 1){
		v2[x] = v2[y];
	}
	else{
		v2[x] = v1[y];
	}

	pai[y] = x;
	pai[i] = x;

	filhos[x].push_back(i);
	for(int j : filhos[y]) filhos[x].push_back(j);

	filhos[y].clear();;

}

static void create(int i){
	pai[i] = i;
	v1[i] = i;
	v2[i] = i;
	filhos[i].push_back(i);
}

static int doQuery(int i,vector<int>& V){

	M.clear();
	M.assign(N,0);

	M[i-1] = 1;
	for(int j : V){
		for(int k : filhos[j]){
			M[k-1] = 1;
		}
	}

	return Query(M);

}

static void divide_and_conquer(int i, vector<int>& V, int caso ){

	//printf("Divide %d %d %d\n",i,(int)V.size(),caso);

	if(caso == 0) return;
	if(V.size() == 1){
		temporario[i].push_back(V[0]);
		return;
	}

	int mid = V.size()/2;
	vector<int> firstHalf,lastHalf;

	for(int j = 0;j<V.size();j++){
		if(j < mid) firstHalf.push_back(V[j]);
		else lastHalf.push_back(V[j]);
	}

	int qtd = doQuery(i,firstHalf);
	if(caso == 1){
		if(qtd == firstHalf.size()){
			//printf("Foi 1 %d\n",i);
			lastHalf.clear();
			divide_and_conquer(i,firstHalf,1);
		}
		else{
			//printf("Foi 2 %d\n",i);
			firstHalf.clear();
			divide_and_conquer(i,lastHalf,1);
		}
	}
	else if(caso == 2){
		if(qtd == firstHalf.size()){
			divide_and_conquer(i,firstHalf,1);
			divide_and_conquer(i,lastHalf,1);
		}
		else if(qtd == firstHalf.size() - 1){
			lastHalf.clear();
			divide_and_conquer(i,firstHalf,2);
		}
		else{
			firstHalf.clear();
			divide_and_conquer(i,lastHalf,2);
		}
	}

}

void Solve(int n){

	//printf("Comeca\n");

	N = n;

	vector<int> M(N);

	create(1);
	for(int i = 2;i<=N;i++){
		//printf("Testando %d\n",i);
		vector<int> V;
		for(int j = 1;j<i;j++) if(find(j) == j) V.push_back(j);
		int qtd = doQuery(i,V);
		if(qtd == V.size() + 1){
			//printf("Solitario %d\n",i);
			create(i);
			continue;
		}
		else if(qtd == V.size()){
			divide_and_conquer(i, V, 1);
			//printf("Achei %d %d\n",i,temporario[i][0]);
			join_case1(temporario[i][0], i );
		}
		else{
			divide_and_conquer(i, V, 2);
			//printf("Achei %d %d %d\n",i,temporario[i][0],temporario[i][1]);
			join_case2(temporario[i][0], temporario[i][1], i );
		}
	}

	int last = -1;
	vector<int> resposta;
	for(int i = 1;i<=N;i++){
		if(grafo[i].size() <= 1){
			resposta.push_back(i);
			break;
		}
	}

	//for(int i = 1;i<=N;i++){
	//	printf("I %d:",i);
	//	for(int j : grafo[i]) printf(" %d",j);
	//	printf("\n");
	//}

	while(resposta.size() != N){
		int x = resposta.back();
		//printf("Adicionando %d\n",x);
		if(grafo[x][0] != last){
			resposta.push_back(grafo[x][0]);
		}
		else{
			resposta.push_back(grafo[x][1]);
		}
		last = x;
	}

	Answer(resposta);

}

Compilation message

library.cpp: In function 'void join_case2(int, int, int)':
library.cpp:56:6: warning: unused variable 'adj_v2x' [-Wunused-variable]
  int adj_v2x = 1 - adj_v1x;
      ^~~~~~~
library.cpp:58:6: warning: unused variable 'adj_v2y' [-Wunused-variable]
  int adj_v2y = 1 - adj_v1y;
      ^~~~~~~
library.cpp: In function 'void divide_and_conquer(int, std::vector<int>&, int)':
library.cpp:125:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0;j<V.size();j++){
                ~^~~~~~~~~
library.cpp:132:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(qtd == firstHalf.size()){
      ~~~~^~~~~~~~~~~~~~~~~~~
library.cpp:144:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(qtd == firstHalf.size()){
      ~~~~^~~~~~~~~~~~~~~~~~~
library.cpp:148:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if(qtd == firstHalf.size() - 1){
           ~~~~^~~~~~~~~~~~~~~~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:174:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(qtd == V.size() + 1){
      ~~~~^~~~~~~~~~~~~~~
library.cpp:179:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if(qtd == V.size()){
           ~~~~^~~~~~~~~~~
library.cpp:206:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(resposta.size() != N){
        ~~~~~~~~~~~~~~~~^~~~

Subtask #1
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	420 KB	Output is correct
2	Correct	21 ms	444 KB	Output is correct
3	Correct	30 ms	504 KB	Output is correct
4	Correct	15 ms	576 KB	Output is correct
5	Correct	27 ms	576 KB	Output is correct
6	Correct	35 ms	576 KB	Output is correct
7	Correct	31 ms	576 KB	Output is correct
8	Correct	29 ms	632 KB	Output is correct
9	Correct	27 ms	632 KB	Output is correct
10	Correct	18 ms	632 KB	Output is correct
11	Correct	2 ms	632 KB	Output is correct
12	Correct	2 ms	676 KB	Output is correct
13	Correct	2 ms	676 KB	Output is correct
14	Correct	2 ms	676 KB	Output is correct
15	Correct	2 ms	676 KB	Output is correct
16	Correct	9 ms	676 KB	Output is correct

Subtask #2
81.0 / 81.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	420 KB	Output is correct
2	Correct	21 ms	444 KB	Output is correct
3	Correct	30 ms	504 KB	Output is correct
4	Correct	15 ms	576 KB	Output is correct
5	Correct	27 ms	576 KB	Output is correct
6	Correct	35 ms	576 KB	Output is correct
7	Correct	31 ms	576 KB	Output is correct
8	Correct	29 ms	632 KB	Output is correct
9	Correct	27 ms	632 KB	Output is correct
10	Correct	18 ms	632 KB	Output is correct
11	Correct	2 ms	632 KB	Output is correct
12	Correct	2 ms	676 KB	Output is correct
13	Correct	2 ms	676 KB	Output is correct
14	Correct	2 ms	676 KB	Output is correct
15	Correct	2 ms	676 KB	Output is correct
16	Correct	9 ms	676 KB	Output is correct
17	Correct	297 ms	700 KB	Output is correct
18	Correct	249 ms	700 KB	Output is correct
19	Correct	279 ms	700 KB	Output is correct
20	Correct	233 ms	720 KB	Output is correct
21	Correct	251 ms	856 KB	Output is correct
22	Correct	279 ms	856 KB	Output is correct
23	Correct	337 ms	856 KB	Output is correct
24	Correct	98 ms	856 KB	Output is correct
25	Correct	248 ms	856 KB	Output is correct
26	Correct	210 ms	856 KB	Output is correct
27	Correct	90 ms	856 KB	Output is correct
28	Correct	53 ms	856 KB	Output is correct
29	Correct	55 ms	856 KB	Output is correct
30	Correct	61 ms	856 KB	Output is correct

답안 #68862

Compilation message

Subtask #1 19.0 / 19.0

Subtask #2 81.0 / 81.0

Subtask #1
19.0 / 19.0

Subtask #2
81.0 / 81.0