Submission #1031317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031317		tvladm2009	Park (JOI17_park)	C++17	100 / 100	234 ms	856 KiB

park

#include "park.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;

int Ask(int A , int B , int Place[]);
void Answer(int A , int B);

const int NMAX = 2000 + 7;

int n;
int places[NMAX];
int vis[NMAX];
vector<int> g[NMAX];
bool rem[NMAX], in[NMAX];

void add_edge(int s, int t) {
    if (s > t) swap(s, t);
    Answer(s, t);
    g[s].push_back(t);
    g[t].push_back(s);
}

bool query(int s, int t) {
    if (s > t) swap(s, t);
    assert(places[s] == 1);
    assert(places[t] == 1);
    return Ask(s, t, places);
}

bool direct(int u) {
    for (int i = 0; i < n; ++i) {
        places[i] = (vis[i] == 1);
    }
    places[u] = 1;
    return query(0, u);
}

int get_next(int u) {
    int l = 0, r = n - 1, sol = -1;
    while (l <= r) {
        int m = (l + r) / 2;
        for (int i = 0; i <= m; ++i) {
            places[i] = (vis[i] != 2);
        }
        for (int i = m + 1; i < n; ++i) {
            places[i] = (vis[i] == 1);
        }
        places[u] = true;
        if (query(0, u)) {
            sol = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return sol;
}

void clear(int u) {
    rem[u] = false;
    for (auto v : g[u]) {
        if (rem[v]) {
            clear(v);
        }
    }
}

vector<int> nodes;

void dfs(int u) {
    nodes.push_back(u);
    in[u] = 1;
    for (auto v : g[u]) {
        if (rem[v] && !in[v]) {
            dfs(v);
        }
    }
}

void find_edge(int u) {
    for (int i = 0; i < n; ++i) {
        rem[i] = (vis[i] == 1);
    }
    for (int root = 0; root < n; ++root) {
        while (rem[root]) {
            for (int i = 0; i < n; ++i) {
                places[i] = rem[i];
            }
            places[u] = 1;
            if (!query(u, root)) {
                clear(root);
                continue;
            }
            nodes.clear();
            for (int i = 0; i < n; ++i) {
                in[i] = false;
            }
            dfs(root);

            int l = 0, r = nodes.size() - 1, sol = -1;
            while (l <= r) {
                int m = (l + r) / 2;
                for (int i = 0; i < nodes.size(); ++i) {
                    places[nodes[i]] = (i <= m);
                }
                if (query(root, u)) {
                    sol = m;
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }
            add_edge(u, nodes[sol]);
            rem[nodes[sol]] = false;
        }
    }
}

void add(int u) {
    vis[u] = 2;
    while (!direct(u)) {
        add(get_next(u));
    }
    find_edge(u);
    vis[u] = 1;
}

void Detect(int T, int N) {
    n = N;
    vis[0] = 1;
    for (int i = 1; i < n; ++i) {
        if (!vis[i]) {
            add(i);
        }
    }
}
/**
#define NMAX  1400
#define DMAX  7
#define QMAX  45000

static int T,N,M,Asktotal,Answertotal;
static int edge_list[NMAX][DMAX];
static int checked[NMAX][DMAX];
static int degree[NMAX];
static int visited[NMAX];
static void WA(int wa_num) {
	printf("Wrong Answer[%d]\n",wa_num);
	exit(0);
}
void Detect(int T, int N);

void Answer(int A, int B) {
	int i;
	if(A < 0||A >= B||B >= N) WA(1);
	for(i = 0 ; i < degree[A] ; i++) {
		if(edge_list[A][i] == B) {
			if(checked[A][i] == 1) WA(3);
			Answertotal++;
			checked[A][i] = 1;
			return;
		}
	}
	WA(2);
}
static void dfs(int now, int Place[]) {
	visited[now] = 1;
	int i;
	for(i = 0 ; i < degree[now] ; i++) {
		if(visited[edge_list[now][i]] == 0 && Place[edge_list[now][i]] == 1) dfs(edge_list[now][i], Place);
	}
}
int Ask(int A, int B, int Place[]) {
	int i;
	Asktotal++;
	if(Asktotal>QMAX) WA(5);
    // if (A < 0) WA(10);
    // if (A >= B) WA(11);
    // if (B >= N) WA(12);
	if(A < 0||A >= B||B >= N) WA(4);
	if(Place[A] != 1) WA(4);
	if(Place[B] != 1) WA(4);
	for(i = 0 ; i < N ; i++) {
		if(Place[i]<0||Place[i]>1) WA(4);
		visited[i] = 0;
	}
	dfs(A, Place);
	return visited[B];
}
int main(int argc, char **argv) {
	int i;
	scanf("%d%d%d",&T,&N,&M);
	Answertotal = 0;
	for(i = 0 ; i < N ; i++) degree[i] = 0;
	for(i = 0 ; i < M ; i++) {
		int ea,eb;
		scanf("%d%d",&ea,&eb);
		checked[ea][degree[ea]] =  0;
		checked[eb][degree[eb]] =  0;
		edge_list[ea][degree[ea]++] = eb;
		edge_list[eb][degree[eb]++] = ea;
	}
	Detect(T, N);
	if(Answertotal<M) WA(6);
	printf("Accepted\n");
	return 0;
}
**/

Compilation message (stderr)

park.cpp: In function 'void find_edge(int)':
park.cpp:106:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |                 for (int i = 0; i < nodes.size(); ++i) {
      |                                 ~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 23 / 23