oj.uz

Submission #218095

# Submission time Handle Problem Language Result Execution time Memory
218095 2020-04-01T07:43:11 Z _7_7_ Stray Cat (JOI20_stray) C++14
15 / 100
 81 ms 20384 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;

vi g[N], res;
queue < int > q;
int n, p[N], d[N];
unordered_map < int, int > gg[N];


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));
	memset(p, -1, sizeof(p));

	q.push(0);
	d[0] = 0;

	while (sz(q)) {
		int v = q.front();
		q.pop();
		for (auto to : g[v])
			if (to != p[v]) {
				if (d[to] == -1) {
					d[to] = d[v] + 1;
					p[to] = v;
					q.push(to);
					res[gg[v][to]] =  d[v] % A;
				} else { 
//					assert(abs(d[to] - d[v]) == 1);
					if (d[to] <= d[v])
						res[gg[v][to]] = d[to] % A; 
				}
			}
	}



	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;

int A, B;

void Init(int _A, int _B) {
	A = _A;
	B = _B;                       	
}

int Move(vi y) {
	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 (A > 2) {
		if (b == A - 1 && a == 0)
			return b;
		return a;
	}
	return a;
		
	
			
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 19320 KB Output is correct
2 Correct 9 ms 4096 KB Output is correct
3 Correct 57 ms 18352 KB Output is correct
4 Correct 75 ms 20384 KB Output is correct
5 Correct 77 ms 20304 KB Output is correct
6 Correct 66 ms 19016 KB Output is correct
7 Correct 64 ms 19200 KB Output is correct
8 Correct 73 ms 19912 KB Output is correct
9 Correct 73 ms 19780 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 19320 KB Output is correct
2 Correct 9 ms 4096 KB Output is correct
3 Correct 57 ms 18352 KB Output is correct
4 Correct 75 ms 20384 KB Output is correct
5 Correct 77 ms 20304 KB Output is correct
6 Correct 66 ms 19016 KB Output is correct
7 Correct 64 ms 19200 KB Output is correct
8 Correct 73 ms 19912 KB Output is correct
9 Correct 73 ms 19780 KB Output is correct
10 Correct 65 ms 16968 KB Output is correct
11 Correct 61 ms 17116 KB Output is correct
12 Correct 61 ms 17136 KB Output is correct
13 Correct 61 ms 17092 KB Output is correct
14 Correct 68 ms 17428 KB Output is correct
15 Correct 69 ms 17812 KB Output is correct
16 Correct 70 ms 20020 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 16996 KB Output is correct
2 Correct 10 ms 4096 KB Output is correct
3 Correct 56 ms 16312 KB Output is correct
4 Correct 78 ms 18212 KB Output is correct
5 Correct 71 ms 18220 KB Output is correct
6 Correct 64 ms 16876 KB Output is correct
7 Correct 63 ms 16860 KB Output is correct
8 Correct 81 ms 17580 KB Output is correct
9 Correct 70 ms 17724 KB Output is correct
10 Correct 71 ms 17356 KB Output is correct
11 Correct 68 ms 17312 KB Output is correct
12 Correct 71 ms 17468 KB Output is correct
13 Correct 66 ms 17472 KB Output is correct
14 Correct 79 ms 17688 KB Output is correct
15 Correct 77 ms 17732 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 16996 KB Output is correct
2 Correct 10 ms 4096 KB Output is correct
3 Correct 56 ms 16312 KB Output is correct
4 Correct 78 ms 18212 KB Output is correct
5 Correct 71 ms 18220 KB Output is correct
6 Correct 64 ms 16876 KB Output is correct
7 Correct 63 ms 16860 KB Output is correct
8 Correct 81 ms 17580 KB Output is correct
9 Correct 70 ms 17724 KB Output is correct
10 Correct 71 ms 17356 KB Output is correct
11 Correct 68 ms 17312 KB Output is correct
12 Correct 71 ms 17468 KB Output is correct
13 Correct 66 ms 17472 KB Output is correct
14 Correct 79 ms 17688 KB Output is correct
15 Correct 77 ms 17732 KB Output is correct
16 Correct 63 ms 15364 KB Output is correct
17 Correct 57 ms 15392 KB Output is correct
18 Correct 59 ms 15440 KB Output is correct
19 Correct 60 ms 15208 KB Output is correct
20 Correct 64 ms 15904 KB Output is correct
21 Correct 61 ms 15644 KB Output is correct
22 Correct 74 ms 17776 KB Output is correct
23 Correct 62 ms 15356 KB Output is correct
24 Correct 61 ms 15352 KB Output is correct

Subtask #5
0 / 5.0

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

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 15248 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -