Submission #57092

#	Time	Username	Problem	Language	Result	Execution time	Memory
57092		Benq	Library (JOI18_library)	C++14	100 / 100	376 ms	864 KiB

library

#include "library.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

using namespace std;

bitset<1001> ADJ[1001];
vi adj[1001], res;
int n;

/*int Query(vi v) {
    int x = sz(v);
    F0R(i,sz(v)) FOR(j,i+1,sz(v)) if (ADJ[v[i]][v[j]]) x --;
    for (int i: v) cout << i << " ";
    cout << "| " << x << "\n";
    return x;
}*/

void addEdge(int x, int y) {
	adj[x].pb(y), adj[y].pb(x);
}

int getEdges(int x, vi v) {
	if (sz(v) == 0) return 0;
	v.pb(x);
	bitset<1001> tmp; for (int i: v) tmp[i] = 1;
	
	vi V(n); for (int i: v) V[i-1] = 1;
	int t = sz(v)-Query(V);

	int already = 0;
	for (int i: v) for (int j: adj[i]) if (tmp[j]) already ++;
	return t-already/2;
}

void solve(int x, vi v, int num) {
    /*cout << x << " | ";
    for (int i: v) cout << i << " ";
    cout << "| " << num << "\n";*/
	if (num == sz(v)) {
		for (int i: v) addEdge(i,x);
		return;
	}
	if (num == 0) return;
	vi v1 = vi(v.begin(),v.begin()+sz(v)/2);
	int num1 = getEdges(x,v1); 
	solve(x,v1,num1);
	solve(x,vi(v.begin()+sz(v)/2,v.end()),num-num1);
}

void dfs(int a, int b) {
	res.pb(a);
	for (int i: adj[a]) if (i != b) dfs(i,a);
}

void ad(int x, int y) { ADJ[x][y] = ADJ[y][x] = 1; }

void Solve(int N) {
    n = N;
	FOR(i,1,N+1) {
		vi v; FOR(j,1,i) if (sz(adj[j]) < 2) v.pb(j);
		solve(i,v,getEdges(i,v));
	}
	int st = 1;
	FOR(i,1,N+1) if (sz(adj[i]) == 1) st = i;
	dfs(st,0);

	Answer(res);
}

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81