oj.uz

Submission #218183

# Submission time Handle Problem Language Result Execution time Memory
218183 2020-04-01T11:42:31 Z _7_7_ Stray Cat (JOI20_stray) C++14
15 / 100
 79 ms 19712 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);
	d[0] = 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) 
			return lst = 1 - lst;
 
 
		if (y[0])
			return lst = 0;
		if (y[1])
			return lst = 1;
		return -1;
	}
 
	if (deg == 1) {
		ok = 1;
		if (lst != -1)
			return -1;
		if (y[0])
			return lst = 0;
//		assert(y[1]);
		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;
//		assert(y[a]);
		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) {
		vv.pb(y[a] == 2 ? a : 1 - a);
	}
		
	vv.pb(a);		
//	assert(y[a]);
	return lst = a;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 18896 KB Output is correct
2 Correct 9 ms 3840 KB Output is correct
3 Correct 55 ms 18284 KB Output is correct
4 Correct 74 ms 19712 KB Output is correct
5 Correct 74 ms 19700 KB Output is correct
6 Correct 63 ms 18628 KB Output is correct
7 Correct 67 ms 18876 KB Output is correct
8 Correct 70 ms 19196 KB Output is correct
9 Correct 70 ms 19188 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 18896 KB Output is correct
2 Correct 9 ms 3840 KB Output is correct
3 Correct 55 ms 18284 KB Output is correct
4 Correct 74 ms 19712 KB Output is correct
5 Correct 74 ms 19700 KB Output is correct
6 Correct 63 ms 18628 KB Output is correct
7 Correct 67 ms 18876 KB Output is correct
8 Correct 70 ms 19196 KB Output is correct
9 Correct 70 ms 19188 KB Output is correct
10 Correct 59 ms 16536 KB Output is correct
11 Correct 63 ms 16804 KB Output is correct
12 Correct 59 ms 16676 KB Output is correct
13 Correct 60 ms 16704 KB Output is correct
14 Correct 59 ms 17004 KB Output is correct
15 Correct 76 ms 17272 KB Output is correct
16 Correct 69 ms 19204 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 16380 KB Output is correct
2 Correct 9 ms 3840 KB Output is correct
3 Correct 59 ms 16180 KB Output is correct
4 Correct 71 ms 17652 KB Output is correct
5 Correct 73 ms 17536 KB Output is correct
6 Correct 60 ms 16448 KB Output is correct
7 Correct 64 ms 16452 KB Output is correct
8 Correct 67 ms 17268 KB Output is correct
9 Correct 67 ms 17028 KB Output is correct
10 Correct 65 ms 16772 KB Output is correct
11 Correct 64 ms 16780 KB Output is correct
12 Correct 65 ms 16764 KB Output is correct
13 Correct 63 ms 16760 KB Output is correct
14 Correct 66 ms 17036 KB Output is correct
15 Correct 70 ms 17036 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 16380 KB Output is correct
2 Correct 9 ms 3840 KB Output is correct
3 Correct 59 ms 16180 KB Output is correct
4 Correct 71 ms 17652 KB Output is correct
5 Correct 73 ms 17536 KB Output is correct
6 Correct 60 ms 16448 KB Output is correct
7 Correct 64 ms 16452 KB Output is correct
8 Correct 67 ms 17268 KB Output is correct
9 Correct 67 ms 17028 KB Output is correct
10 Correct 65 ms 16772 KB Output is correct
11 Correct 64 ms 16780 KB Output is correct
12 Correct 65 ms 16764 KB Output is correct
13 Correct 63 ms 16760 KB Output is correct
14 Correct 66 ms 17036 KB Output is correct
15 Correct 70 ms 17036 KB Output is correct
16 Correct 57 ms 14956 KB Output is correct
17 Correct 55 ms 14952 KB Output is correct
18 Correct 57 ms 14768 KB Output is correct
19 Correct 57 ms 14888 KB Output is correct
20 Correct 64 ms 15340 KB Output is correct
21 Correct 61 ms 15192 KB Output is correct
22 Correct 64 ms 17028 KB Output is correct
23 Correct 61 ms 14892 KB Output is correct
24 Correct 59 ms 14880 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4096 KB Output is correct
2 Incorrect 9 ms 3840 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 14608 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 14836 KB Output is correct
2 Incorrect 56 ms 15664 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -