oj.uz

Submission #72807

# Submission time Handle Problem Language Result Execution time Memory
72807 2018-08-27T02:32:55 Z Benq Park (JOI17_park) C++14
77 / 100
 167 ms 2952 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

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

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
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;


#define NMAX  1400
#define DMAX  1400
#define QMAX  45000

// #define LOCAL 

#ifndef LOCAL
	#include "park.h"
#else 
	void Answer(int A, int B);
	int Ask(int A, int B, int Place[]);
#endif 

int n;

static int Place[1400];

// BEGIN UTILITY
bool ok(int a, int b, vi x) {
    if (a > b) swap(a,b);
    F0R(i,1400) Place[i] = 0;
    Place[a] = Place[b] = 1;
    for (int i: x) Place[i] = 1;
    return Ask(a,b,Place);
}
bool checkEdge(int a, int b) { return ok(a,b,{}); }
vi merge(vi a, vi b) {
    a.insert(a.end(),all(b));
    return a;
}
void answer(int l, int r) {
    if (l > r) swap(l,r);
    Answer(l,r);
}
// END UTILITY 

bool inTree[1400];

vi divi(int l, int r) {
    // cout << "BLAH " << l << " " << r << "\n";
    if (checkEdge(l,r)) { answer(l,r); return {r}; }
    vi tmp; 
    F0R(i,n) if (i != l && i != r && !inTree[i]) tmp.pb(i);
    int lo = 1, hi = sz(tmp);
    while (lo < hi) {
        int mid = (lo+hi)/2;
        if (ok(l,r,vi(tmp.begin(),tmp.begin()+mid))) hi = mid;
        else lo = mid+1;
    }
    return merge(divi(l,tmp[lo-1]),divi(tmp[lo-1],r));
}

int getAdj(int x, vi cur) {
    vi bad; F0R(i,n) if (!inTree[i] && i != x) bad.pb(i);
    /*if (x == 3) {
        cout << "QQQQ ";
        for (int i: bad) cout << i << " ";
    }*/
    int lo = 1, hi = sz(cur);
    while (lo < hi) {
        int mid = (lo+hi)/2;
        if (ok(cur[0],x,merge(bad,vi(cur.begin(),cur.begin()+mid)))) hi = mid;
        else lo = mid+1;
    }
    return cur[lo-1];
}

void Detect(int T, int _n) {
    n = _n;
    if (T == 1) {
        F0R(i,n) FOR(j,i+1,n) if (checkEdge(i,j)) Answer(i,j);
        return;
    }
    inTree[0] = 1;
    vi cur = {0};
    int nex = 0;
    while (nex < n) {
        while (nex < n && inTree[nex]) nex ++;
        if (nex == n) return;
        int x = getAdj(nex,cur);
        vi t = divi(x,nex);
        for (int i: t) { cur.pb(i); inTree[i] = 1; }
    }
}

#ifdef LOCAL 

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 Answer(int A, int B) {
	int i;
	cout << A << " " << B << "\n";
	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[], bool z = 0) {
	visited[now] = 1;
	// if (z) cout << "AAA " << now << "\n";
	int i;
	for(i = 0 ; i < degree[now] ; i++) {
		if(visited[edge_list[now][i]] == 0 && Place[edge_list[now][i]] == 1) {
		    // if (edge_list[now][i] == 51) cout << "BBB " << now << " " << i << " " << edge_list[now][i] << "\n";
		    dfs(edge_list[now][i], Place,z);
		}
	}
}

int Ask(int A, int B, int Place[]) {
    /*if (A == 1 && B == 51) {
        cout << "AA " << A << " " << B << "\n";
        F0R(i,1400) if (Place[i]) cout << "RES " << i << "\n";
    }*/
	int i;
	Asktotal++;
	if(Asktotal>QMAX) WA(5);
	if(A < 0||A >= B||B >= N) {
	    cout << A << " " << 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);
	/*if (A == 1 && B == 51) {
	    cout << "BB " << B << " " << visited[B];
	    exit(0);
	}*/
	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;
		/*if (eb == 10) {
		    cout << "RU " << edge_list[10][0] << "\n";
		}
		if (ea == 10 || eb == 10) cout << "ZZZZZ " << ea << " " << eb << "\n";*/
	}
	Detect(T, N);
	if(Answertotal<M) WA(6);
	printf("Accepted\n");
	return 0;
}

#endif

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 15 ms 380 KB Output is correct
3 Correct 17 ms 412 KB Output is correct
4 Correct 13 ms 412 KB Output is correct
5 Correct 13 ms 488 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 760 KB Output is correct
2 Correct 122 ms 760 KB Output is correct
3 Correct 122 ms 2952 KB Output is correct
4 Correct 75 ms 2952 KB Output is correct
5 Correct 54 ms 2952 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 2952 KB Output is correct
2 Correct 148 ms 2952 KB Output is correct
3 Correct 159 ms 2952 KB Output is correct
4 Correct 148 ms 2952 KB Output is correct
5 Correct 167 ms 2952 KB Output is correct
6 Correct 145 ms 2952 KB Output is correct
7 Correct 163 ms 2952 KB Output is correct
8 Correct 166 ms 2952 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2952 KB Output is correct
2 Correct 143 ms 2952 KB Output is correct
3 Correct 159 ms 2952 KB Output is correct
4 Correct 91 ms 2952 KB Output is correct
5 Correct 123 ms 2952 KB Output is correct
6 Correct 74 ms 2952 KB Output is correct
7 Correct 82 ms 2952 KB Output is correct
8 Correct 108 ms 2952 KB Output is correct
9 Correct 97 ms 2952 KB Output is correct
10 Correct 105 ms 2952 KB Output is correct
11 Correct 126 ms 2952 KB Output is correct
12 Correct 166 ms 2952 KB Output is correct
13 Correct 72 ms 2952 KB Output is correct
14 Correct 117 ms 2952 KB Output is correct
15 Correct 73 ms 2952 KB Output is correct
16 Correct 133 ms 2952 KB Output is correct
17 Correct 50 ms 2952 KB Output is correct
18 Correct 109 ms 2952 KB Output is correct
19 Correct 70 ms 2952 KB Output is correct
20 Correct 110 ms 2952 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 148 ms 2952 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -