oj.uz

Submission #212353

# Submission time Handle Problem Language Result Execution time Memory
212353 2020-03-22T18:15:51 Z egorlifar Stray Cat (JOI20_stray) C++17
5 / 100
 82 ms 18644 KB 
#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;
}

#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 13160 KB Program didn't exit properly, or you printed something to stdout.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 13160 KB Program didn't exit properly, or you printed something to stdout.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 13296 KB Program didn't exit properly, or you printed something to stdout.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 13296 KB Program didn't exit properly, or you printed something to stdout.
2 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10240 KB Output is correct
2 Correct 11 ms 9984 KB Output is correct
3 Correct 13 ms 10240 KB Output is correct
4 Correct 13 ms 10240 KB Output is correct
5 Correct 13 ms 10240 KB Output is correct
6 Correct 13 ms 10240 KB Output is correct
7 Correct 13 ms 10240 KB Output is correct
8 Correct 14 ms 10240 KB Output is correct
9 Correct 12 ms 10240 KB Output is correct
10 Correct 13 ms 10240 KB Output is correct
11 Correct 15 ms 10344 KB Output is correct
12 Correct 13 ms 10192 KB Output is correct
13 Correct 13 ms 10240 KB Output is correct
14 Correct 13 ms 10240 KB Output is correct
15 Correct 13 ms 10240 KB Output is correct
16 Correct 15 ms 10240 KB Output is correct
17 Correct 13 ms 10240 KB Output is correct
18 Correct 13 ms 10272 KB Output is correct
19 Correct 13 ms 10240 KB Output is correct
20 Correct 13 ms 10240 KB Output is correct
21 Correct 12 ms 10240 KB Output is correct
22 Correct 13 ms 10240 KB Output is correct
23 Correct 15 ms 10240 KB Output is correct
24 Correct 12 ms 10192 KB Output is correct
25 Correct 12 ms 10240 KB Output is correct
26 Correct 13 ms 10240 KB Output is correct
27 Correct 13 ms 10240 KB Output is correct
28 Correct 13 ms 10240 KB Output is correct

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 15728 KB Output is correct
2 Correct 65 ms 16788 KB Output is correct
3 Correct 13 ms 10240 KB Output is correct
4 Correct 66 ms 15716 KB Output is correct
5 Correct 82 ms 18268 KB Output is correct
6 Correct 82 ms 18148 KB Output is correct
7 Incorrect 60 ms 17404 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 15604 KB Output is correct
2 Correct 72 ms 16480 KB Output is correct
3 Correct 14 ms 10496 KB Output is correct
4 Correct 52 ms 15892 KB Output is correct
5 Correct 74 ms 18644 KB Output is correct
6 Correct 81 ms 18572 KB Output is correct
7 Incorrect 59 ms 17740 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -