oj.uz

Submission #72991

# Submission time Handle Problem Language Result Execution time Memory
72991 2018-08-27T12:21:10 Z Benq Park (JOI17_park) C++14
100 / 100
 266 ms 2848 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;
}

bool inTree[1400];
vi adj[1400], tmp;

void answer(int l, int r) {
    if (l > r) swap(l,r);
    adj[l].pb(r), adj[r].pb(l);
    Answer(l,r);
}
// END UTILITY 


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, bool b = 1) {
    vi bad; F0R(i,n) if (!inTree[i] && i != x) bad.pb(i);
    int lo = 1, hi = sz(cur);
    while (lo < hi) {
        int mid = (lo+hi)/2;
        if (ok(cur[0],x,b?merge(bad,vi(cur.begin(),cur.begin()+mid)):vi(cur.begin(),cur.begin()+mid))) hi = mid;
        else lo = mid+1;
    }
    return cur[lo-1];
}

bool OK[1400];

void dfs(int i) {
    tmp.pb(i); OK[i] = 0;
    for (int j: adj[i]) if (OK[j]) dfs(j);
}

vector<vi> rem(vi cur, int ol) {
    F0R(i,1400) OK[i] = 0;
    for (int i: cur) if (i != ol) OK[i] = 1;
    vector<vi> res;
    for (int i: cur) if (OK[i]) {
        dfs(i);
        res.pb(tmp); tmp = {};
    }
    return res;
}

void tri(vi x, int ne) {
    if (!sz(x)) return;
    if (!ok(x[0],ne,x)) return;
    int y = getAdj(ne,x,0);
    answer(ne,y);
    for (auto z: rem(x,y)) tri(z,ne);
}

void ad(vi cur, int ne, int ol) {
    auto a = rem(cur,ol);
    for (auto x: a) tri(x,ne);
}

void Detect(int T, int _n) {
    n = _n;
    
    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) { inTree[i] = 1; ad(cur,i,x); cur.pb(i); x = i;  }
        //cout << "HI "; for (int i: cur) cout << i << " ";
        //cout << "\n";
    }
}

#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 2 ms 376 KB Output is correct
2 Correct 9 ms 620 KB Output is correct
3 Correct 9 ms 684 KB Output is correct
4 Correct 19 ms 684 KB Output is correct
5 Correct 40 ms 684 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 800 KB Output is correct
2 Correct 141 ms 800 KB Output is correct
3 Correct 158 ms 2848 KB Output is correct
4 Correct 79 ms 2848 KB Output is correct
5 Correct 78 ms 2848 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 2848 KB Output is correct
2 Correct 201 ms 2848 KB Output is correct
3 Correct 203 ms 2848 KB Output is correct
4 Correct 205 ms 2848 KB Output is correct
5 Correct 214 ms 2848 KB Output is correct
6 Correct 214 ms 2848 KB Output is correct
7 Correct 190 ms 2848 KB Output is correct
8 Correct 222 ms 2848 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 2848 KB Output is correct
2 Correct 189 ms 2848 KB Output is correct
3 Correct 180 ms 2848 KB Output is correct
4 Correct 149 ms 2848 KB Output is correct
5 Correct 147 ms 2848 KB Output is correct
6 Correct 119 ms 2848 KB Output is correct
7 Correct 124 ms 2848 KB Output is correct
8 Correct 162 ms 2848 KB Output is correct
9 Correct 146 ms 2848 KB Output is correct
10 Correct 144 ms 2848 KB Output is correct
11 Correct 158 ms 2848 KB Output is correct
12 Correct 180 ms 2848 KB Output is correct
13 Correct 99 ms 2848 KB Output is correct
14 Correct 165 ms 2848 KB Output is correct
15 Correct 144 ms 2848 KB Output is correct
16 Correct 205 ms 2848 KB Output is correct
17 Correct 78 ms 2848 KB Output is correct
18 Correct 192 ms 2848 KB Output is correct
19 Correct 109 ms 2848 KB Output is correct
20 Correct 158 ms 2848 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 2848 KB Output is correct
2 Correct 236 ms 2848 KB Output is correct
3 Correct 207 ms 2848 KB Output is correct
4 Correct 173 ms 2848 KB Output is correct
5 Correct 266 ms 2848 KB Output is correct
6 Correct 106 ms 2848 KB Output is correct
7 Correct 188 ms 2848 KB Output is correct
8 Correct 139 ms 2848 KB Output is correct
9 Correct 149 ms 2848 KB Output is correct
10 Correct 203 ms 2848 KB Output is correct
11 Correct 171 ms 2848 KB Output is correct
12 Correct 150 ms 2848 KB Output is correct
13 Correct 159 ms 2848 KB Output is correct
14 Correct 224 ms 2848 KB Output is correct
15 Correct 146 ms 2848 KB Output is correct
16 Correct 187 ms 2848 KB Output is correct
17 Correct 77 ms 2848 KB Output is correct
18 Correct 146 ms 2848 KB Output is correct