oj.uz

Submission #218158

# Submission time Handle Problem Language Result Execution time Memory
218158 2020-04-01T10:53:19 Z _7_7_ Stray Cat (JOI20_stray) C++14
0 / 100
 77 ms 19164 KB 
#include "Anthony.h"
#include <bits/stdc++.h>                                           
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 333;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 2e4 + 11;
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;
 
namespace {
vi g[N], res, G = {0, 1, 0, 0, 1, 1};
unordered_map < int, int > gg[N];
queue < int > q;
int n, d[N];
}


void dfs (int v, int par = 0, int c = 0) {
	int son = sz(g[v]) + 1 - (!v), cc;
	if (son == 1)
		cc = (c + 1) % 6;
	else
		cc = 1 - G[c];

	for (auto to : g[v])
		if (to != par) {
			res[gg[v][to]] = G[c];
			dfs(to, v, cc);
		}
}

 
 
vi Mark(int _n, int m, int A, int B, vi U, vi V) {
	n = _n;
	res.resize(m);
 
	for (int i = 0; i < m; ++i) {
		g[V[i]].pb(U[i]); 
		g[U[i]].pb(V[i]);
		gg[V[i]][U[i]] = gg[U[i]][V[i]] = i;
	}
	
	memset(d, -1, sizeof(d));
	q.push(0);
	while (sz(q)) {
		int v = q.front();
		q.pop();
		for (auto to : g[v])
			if (d[to] == -1) {
				d[to] = d[v] + 1;
				q.push(to);
			}
	}

	if (A > 2) 
		for (int i = 0; i < m; ++i)
			res[i] = min(d[V[i]], d[U[i]]) % A;
	else 
		dfs(0);
	
 
	return res;
}
#include "Catherine.h"
#include <bits/stdc++.h>                                           
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 333;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 3e5 + 11;
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;
 
namespace {
vi vv, G = {0, 1, 0, 0, 1, 1};
int A, B, timer, lst = -1;
bool ok;
}

 
void Init(int _A, int _B) {
	A = _A;
	B = _B;                       	
}
 
int Move(vi y) {
    if (A > 2) { 
		int a = -1, b = -1;
		for (int i = 0; i < sz(y); ++i)
			if (y[i]) {
				if (a == -1)
					a = i;
				else if (b == -1)
					b = i;
				else 
					assert(0);			
			}
		if (b == -1)
			return a;
 	
		if (b == A - 1 && a == 0)
			return b;
		return a;
	}

	++timer;
	int deg = y[0] + y[1] + (lst > -1);
	if (ok) {
		if (deg >= 3) {
			lst = 1 - lst;
			return lst;
		}

		if (y[0])
			return lst = 0;
		return lst = 1;
	}

	if (deg == 1) {
		ok = 1;
		if (lst != -1)
			return -1;
		if (y[0])
			return lst = 0;
		return lst = 1;
	}
	            
	if (deg > 2) {
		ok = 1;
		if (lst > -1)
			++y[lst];
		
		int a = y[0] == 1 ? 0 : 1;
		assert(y[a] == 1);
		if (lst == a)
			return -1;
		return lst = a;					
	}

	//deg == 2
	if (timer == 4) {
		int a = y[0] ? 0 : 1;
		vv.pb(a);
		bool found = 0;
		for (int i = 0; i < 6; ++i) {
			bool tmp = 1;
			for (int j = 0; j < 5; ++j)		
				if (vv[j] != G[(j + i) % 6]) {
					tmp = 0;
					break;
				}

			if (tmp)
				found = 1;
		}

		ok = 1;
		if (found) 
			return lst = a;
		return -1;						
	}

	//deg = 2 and timer <= 3
	int a = y[0] ? 0 : 1;

	if (timer == 1) {
		--y[a];
		vv.pb(y[a] ? a : 1 - a);
	}
		
	vv.pb(a);		
	return lst = a;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 19164 KB Output is correct
2 Correct 10 ms 3840 KB Output is correct
3 Incorrect 56 ms 18192 KB Wrong Answer [6]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 19164 KB Output is correct
2 Correct 10 ms 3840 KB Output is correct
3 Incorrect 56 ms 18192 KB Wrong Answer [6]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 16724 KB Output is correct
2 Correct 10 ms 3840 KB Output is correct
3 Incorrect 65 ms 16448 KB Wrong Answer [6]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 16724 KB Output is correct
2 Correct 10 ms 3840 KB Output is correct
3 Incorrect 65 ms 16448 KB Wrong Answer [6]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4096 KB Output is correct
2 Correct 10 ms 4096 KB Output is correct
3 Correct 14 ms 4096 KB Output is correct
4 Correct 11 ms 4096 KB Output is correct
5 Correct 11 ms 4352 KB Output is correct
6 Correct 11 ms 4096 KB Output is correct
7 Incorrect 11 ms 4096 KB Wrong Answer [5]
8 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 15120 KB Output is correct
2 Correct 67 ms 16460 KB Output is correct
3 Correct 11 ms 4096 KB Output is correct
4 Correct 60 ms 14888 KB Output is correct
5 Correct 74 ms 18484 KB Output is correct
6 Correct 71 ms 18484 KB Output is correct
7 Incorrect 63 ms 17580 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 14936 KB Output is correct
2 Correct 64 ms 16252 KB Output is correct
3 Correct 10 ms 3840 KB Output is correct
4 Correct 54 ms 15008 KB Output is correct
5 Correct 77 ms 18480 KB Output is correct
6 Correct 70 ms 18324 KB Output is correct
7 Incorrect 59 ms 17592 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -