Submission #212353

#	Time	Username	Problem	Language	Result	Execution time	Memory
212353		egorlifar	Stray Cat (JOI20_stray)	C++17	5 / 100	82 ms	18644 KiB

Anthony

#include "Anthony.h"
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
       
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define rank rank228
#define y1 y1228
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
using ll = long long;
using ld = long double;
const int MAXN = 200228;


vector<pair<int, int> > g[MAXN];
int dist[MAXN];
bool used[MAXN];
int c[6] = {1, 1, 0, 0, 1, 0};

vector<int> st;
int head[MAXN];
int ps[MAXN];
bool xored[MAXN];


void dfs(int u, int pr = -1) {
	int cnt = 0;
	int deg = sz(g[u]);
	for (auto h: g[u]) {
		if (h.first != pr) {
			if (pr == -1) {
				st[h.second] = 0;
				head[h.first] = h.second;
				ps[h.second] = 0;
			} else {
				if (deg >= 3) {
					st[h.second] = st[head[u]] ^ 1;
					head[h.first] = h.second;
					if (st[h.second] == 1) {
						ps[h.second] = 0;
					} else {
						ps[h.second] = 2;
					}
				} else { 
					st[h.second] = c[(ps[head[u]] + 1) % 6];
					ps[h.second] = (ps[head[u]] + 1) % 6;
					head[h.first] = h.second;
				}
			}
			dfs(h.first, u);
		}
	}
}

vector<int> Mark(int n, int m, int A, int B, vector<int> U, vector<int> V) {
 	for (int i = 0; i < m; i++) {
 		g[U[i]].pb({V[i], i});
 		g[V[i]].pb({U[i], i});
 	}
 	if (A == 2) {
 		st.resize(m);
 		dfs(0);
 		return st;	
 	}
 	for (int i = 0; i < n; i++) {
 		dist[i] = 0;
 		used[i] = false;
 	}
 	vector<int> st(m, 0);
 	queue<int> q;
 	q.push(0);
 	dist[0] = 0;
 	used[0] = true;
 	while (!q.empty()) {
 		int a = q.front();
 		q.pop();
 		for (auto h: g[a]) {
 			if (!used[h.first]) {
 				st[h.second] = dist[a] % 3;
 				dist[h.first] = dist[a] +1;
 				used[h.first] = true;
 				q.push(h.first);
 			}
 		}
 	}
 	for (int i = 1; i < n; i++) {
 		int pos = (dist[i] - 1) % 3;
 		for (auto h: g[i]) {
 			if (dist[i] == dist[h.first] + 1) {
 				st[h.second] = pos;
 			} else {
	 			st[h.second] = (pos + 1) % 3;
 			}
 		}
 	}
 	for (auto x: st) {
 		cout << x << endl;
 	}
  	return st;
}

Catherine

#include "Catherine.h"
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
       
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define rank rank228
#define y1 y1228
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
using ll = long long;
using ld = long double;



bool kek = false;
int cs[12] = {1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0};

void Init(int A, int B) {
	if (A == 2) {
		kek = true;
	}
	//reverse(cs, cs + 12);
}

int f = 1;
int last;
vector<int> cur;
bool bad = false;

int Move(vector<int> y) {
	if (kek) {
		f--;
	//	cout << y[0] << ' ' << y[1] << endl;
		if (y[0] == 0 && y[1] == 0) {
			bad = false;
			return -1;    
		}
		
		int sum = y[0] + y[1];
		if ((f == 0 && sum >= 3) || (f < 0 && sum >= 2)) {
			if (y[0] == 0 || y[1] == 0) {
				bad = false;
				return -1;
			}
			bad = false;
			if (f < 0) {
				last ^= 1;
				return last;
			}
			last = y[0] < y[1] ? 0: 1;
			return last; 
		}
		if (f == 0) {
			bad = true;
			last = y[1] ? 1: 0;
			if (y[last ^ 1]) {
				cur.pb(last ^ 1);
			} else if (y[last] >= 2) {
				cur.pb(last);
			}
			if (sum == 1) {
				bad = false;
			}
			cur.pb(last); 
			return last;
		}
		if (y[0] >= 2) {
			bad = false;
			return -1;
		}
		if (y[1] >= 2) {
			bad = false;
			return -1;
		}
		if (!bad) {
			last = y[1] ? 1: 0;
			return last;
		}
		last = y[1] ? 1: 0;
		cur.pb(last);
		bool ok = false;
		for (int i = 0; i <= 12 - sz(cur); i++) {
			bool bad = false;
			for (int j = 0; j < sz(cur); j++) {
				if (cur[sz(cur) - j - 1] != cs[i + j]) {
					bad = true;
					break;
				}
			}
			if (!bad) {
				ok = true;
			}
		}
		if (!ok) {
			bad = false;
			return -1;
		}
		return last;
	}	
	vector<int> st;
	for (int i = 0; i < sz(y); i++) {
		if (y[i] != 0) {
			st.pb(i);
		}
	}
	if (sz(st) == 0) {
		return -1;
	}
	if (sz(st) == 1) {
		return st[0];
	}
	if ((st[0] + 1) % 3 != st[1]) {
		swap(st[0], st[1]);
	}
  	return st[0];
}

Compilation message (stderr)

Anthony.cpp: In function 'void dfs(int, int)':
Anthony.cpp:57:6: warning: unused variable 'cnt' [-Wunused-variable]
  int cnt = 0;
      ^~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 2
• Subtask 3: 0 / 2
• Subtask 4: 0 / 9
• Subtask 5: 5 / 5
• Subtask 6: 0 / 71
• Subtask 7: 0 / 9