oj.uz

Submission #565997

# Submission time Handle Problem Language Result Execution time Memory
565997 2022-05-21T16:11:01 Z errorgorn Stray Cat (JOI20_stray) C++17
100 / 100
 58 ms 16732 KB 
#include "Anthony.h"

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

namespace {
	bool st;
	int n,m;
	vector<int> al[20005];
	
	int w[20005];
	queue<int> q;
	
	int d[20005];
	int pat[20005];
	int col[20005];
	
	void dfs(int i,int p){
		int child=0;
		for (auto it:al[i]){
			if (it==p) continue;
			child++;
		}
		
		for (auto it:al[i]){
			if (it==p) continue;
			
			if (child>1){
				pat[it]=col[it]=col[i]^1;
			}
			else{
				pat[it]=(pat[i]+1)%7;
				
				vector<int> C={0,1,0,0,1,1,1};
				col[it]=C[pat[it]];
			}
			
			d[it]=d[i]+1;
			dfs(it,i);
		}
	}
}

vector<signed> Mark(signed N, signed M, signed A, signed B,
                      vector<signed> U, vector<signed> V) {
						  
	
	st=(A>=3);
	n=N,m=M;
	rep(x,0,m){
		al[U[x]].pub(V[x]);
		al[V[x]].pub(U[x]);
	}
	
	if (st){
		memset(w,-1,sizeof(w));
		q.push(0);
		w[0]=0;
		
		while (!q.empty()){
			int u=q.front(); q.pop();
			for (auto it:al[u]) if (w[it]==-1){
				w[it]=w[u]+1;
				q.push(it);
			}
		}
		
		vector<signed> res;
		rep(x,0,m){
			res.pub(min(w[U[x]],w[V[x]])%3);
			//cout<<res.back()<<" "<<U[x]<<" "<<V[x]<<endl;
		}
		return res;
	}
	else{
		dfs(0,-1);
		
		vector<signed> res;
		rep(x,0,m){
			if (d[U[x]]>d[V[x]]) swap(U[x],V[x]);
			res.pub(col[V[x]]);
		}
		
		//for (auto it:res) cout<<it<<" "; cout<<endl;
		return res;
	}
}

#include "Catherine.h"

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

namespace {
	bool st;
	int PREV=-1;
	
	set<string> good={
		"01001",
		"10011",
		"00111",
		"01110",
		"11101",
		"11010",
		"10100"
	};
	
	bool dir=false;
	string s="";
}

void Init(signed A, signed B) {
	st=(A>=3);
}

signed Move(vector<signed> y) {
	if (st){
		vector<int> v;
		rep(x,0,3) if (y[x] || PREV==x) v.pub(x);
		sort(all(v));
		
		if (sz(v)==1){
			return PREV=v[0];
		}
		else if (v[1]==1){
			return PREV=0;
		}
		else if (v[0]==1){
			return PREV=1;
		}
		else{
			return PREV=2;
		}
	}
	else{
		int tot=(PREV!=-1);
		rep(x,0,2) tot+=y[x];
		
		if (tot>=3){
			dir=true;
			if (PREV!=-1) y[PREV]++;
			rep(x,0,2) if (y[x]==1){
				if (PREV!=x) return PREV=x;
				else return -1;
			}
		}
		else if (tot==1){
			dir=true;
			if (PREV!=-1) y[PREV]++;
			rep(x,0,2) if (y[x]==1){
				if (PREV!=x) return PREV=x;
				else return -1;
			}
		}
		else if (dir){
			rep(x,0,2) if (y[x]==1) return PREV=x;
		}
		else{
			if (s==""){
				rep(x,2,0) rep(z,0,y[x]) s+='0'+x;
				//cout<<s<<endl;
				rep(x,0,2) if (y[x]) return PREV=x;
			}
			else{
				rep(x,0,2) rep(z,0,y[x]) s+='0'+x;
				//cout<<s<<endl;
				if (sz(s)==5){
					dir=true;
					if (!good.count(s)){
						rep(x,0,2) if (y[x]==1) return PREV=x;
					}
					else{
						return -1; //PREV is same
					}
				}
				else{
					rep(x,0,2) if (y[x]) return PREV=x;
				}
			}
		}
		
	}
}

Compilation message

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:111:1: warning: control reaches end of non-void function [-Wreturn-type]
  111 | }
      | ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 15732 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 28 ms 15076 KB Output is correct
4 Correct 49 ms 16732 KB Output is correct
5 Correct 47 ms 16712 KB Output is correct
6 Correct 37 ms 15468 KB Output is correct
7 Correct 37 ms 15484 KB Output is correct
8 Correct 41 ms 16096 KB Output is correct
9 Correct 41 ms 16160 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 15732 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 28 ms 15076 KB Output is correct
4 Correct 49 ms 16732 KB Output is correct
5 Correct 47 ms 16712 KB Output is correct
6 Correct 37 ms 15468 KB Output is correct
7 Correct 37 ms 15484 KB Output is correct
8 Correct 41 ms 16096 KB Output is correct
9 Correct 41 ms 16160 KB Output is correct
10 Correct 37 ms 13664 KB Output is correct
11 Correct 35 ms 13632 KB Output is correct
12 Correct 33 ms 13612 KB Output is correct
13 Correct 41 ms 13576 KB Output is correct
14 Correct 36 ms 13880 KB Output is correct
15 Correct 40 ms 14124 KB Output is correct
16 Correct 44 ms 16172 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 13164 KB Output is correct
2 Correct 1 ms 1160 KB Output is correct
3 Correct 30 ms 12824 KB Output is correct
4 Correct 44 ms 14460 KB Output is correct
5 Correct 45 ms 14344 KB Output is correct
6 Correct 33 ms 13216 KB Output is correct
7 Correct 33 ms 13192 KB Output is correct
8 Correct 43 ms 13940 KB Output is correct
9 Correct 40 ms 13800 KB Output is correct
10 Correct 37 ms 13572 KB Output is correct
11 Correct 37 ms 13580 KB Output is correct
12 Correct 39 ms 13512 KB Output is correct
13 Correct 37 ms 13676 KB Output is correct
14 Correct 40 ms 13956 KB Output is correct
15 Correct 39 ms 13876 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 13164 KB Output is correct
2 Correct 1 ms 1160 KB Output is correct
3 Correct 30 ms 12824 KB Output is correct
4 Correct 44 ms 14460 KB Output is correct
5 Correct 45 ms 14344 KB Output is correct
6 Correct 33 ms 13216 KB Output is correct
7 Correct 33 ms 13192 KB Output is correct
8 Correct 43 ms 13940 KB Output is correct
9 Correct 40 ms 13800 KB Output is correct
10 Correct 37 ms 13572 KB Output is correct
11 Correct 37 ms 13580 KB Output is correct
12 Correct 39 ms 13512 KB Output is correct
13 Correct 37 ms 13676 KB Output is correct
14 Correct 40 ms 13956 KB Output is correct
15 Correct 39 ms 13876 KB Output is correct
16 Correct 32 ms 11592 KB Output is correct
17 Correct 30 ms 11704 KB Output is correct
18 Correct 31 ms 11708 KB Output is correct
19 Correct 33 ms 11540 KB Output is correct
20 Correct 36 ms 12232 KB Output is correct
21 Correct 34 ms 12008 KB Output is correct
22 Correct 38 ms 13948 KB Output is correct
23 Correct 32 ms 11756 KB Output is correct
24 Correct 34 ms 11668 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1292 KB Output is correct
2 Correct 1 ms 1032 KB Output is correct
3 Correct 2 ms 1284 KB Output is correct
4 Correct 2 ms 1420 KB Output is correct
5 Correct 2 ms 1412 KB Output is correct
6 Correct 2 ms 1416 KB Output is correct
7 Correct 2 ms 1420 KB Output is correct
8 Correct 2 ms 1420 KB Output is correct
9 Correct 2 ms 1412 KB Output is correct
10 Correct 2 ms 1420 KB Output is correct
11 Correct 2 ms 1420 KB Output is correct
12 Correct 2 ms 1412 KB Output is correct
13 Correct 2 ms 1412 KB Output is correct
14 Correct 2 ms 1412 KB Output is correct
15 Correct 2 ms 1420 KB Output is correct
16 Correct 2 ms 1412 KB Output is correct
17 Correct 2 ms 1436 KB Output is correct
18 Correct 2 ms 1420 KB Output is correct
19 Correct 2 ms 1420 KB Output is correct
20 Correct 2 ms 1412 KB Output is correct
21 Correct 2 ms 1412 KB Output is correct
22 Correct 2 ms 1424 KB Output is correct
23 Correct 2 ms 1412 KB Output is correct
24 Correct 2 ms 1420 KB Output is correct
25 Correct 2 ms 1420 KB Output is correct
26 Correct 2 ms 1412 KB Output is correct
27 Correct 2 ms 1412 KB Output is correct
28 Correct 2 ms 1412 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 11708 KB Output is correct
2 Correct 47 ms 13672 KB Output is correct
3 Correct 1 ms 1032 KB Output is correct
4 Correct 27 ms 11592 KB Output is correct
5 Correct 47 ms 15924 KB Output is correct
6 Correct 43 ms 15860 KB Output is correct
7 Correct 35 ms 14908 KB Output is correct
8 Correct 35 ms 14876 KB Output is correct
9 Correct 46 ms 15768 KB Output is correct
10 Correct 43 ms 15760 KB Output is correct
11 Correct 41 ms 15964 KB Output is correct
12 Correct 47 ms 15840 KB Output is correct
13 Correct 49 ms 15704 KB Output is correct
14 Correct 41 ms 15744 KB Output is correct
15 Correct 42 ms 15964 KB Output is correct
16 Correct 58 ms 15800 KB Output is correct
17 Correct 48 ms 15496 KB Output is correct
18 Correct 39 ms 15564 KB Output is correct
19 Correct 40 ms 15560 KB Output is correct
20 Correct 39 ms 15560 KB Output is correct
21 Correct 40 ms 15496 KB Output is correct
22 Correct 38 ms 15548 KB Output is correct
23 Correct 32 ms 11880 KB Output is correct
24 Correct 31 ms 11880 KB Output is correct
25 Correct 33 ms 12480 KB Output is correct
26 Correct 33 ms 12516 KB Output is correct
27 Correct 37 ms 13852 KB Output is correct
28 Correct 41 ms 13752 KB Output is correct
29 Correct 38 ms 13888 KB Output is correct
30 Correct 38 ms 13844 KB Output is correct
31 Correct 35 ms 11764 KB Output is correct
32 Correct 36 ms 11744 KB Output is correct
33 Correct 34 ms 12312 KB Output is correct
34 Correct 39 ms 12432 KB Output is correct
35 Correct 42 ms 13576 KB Output is correct
36 Correct 47 ms 13660 KB Output is correct
37 Correct 39 ms 13620 KB Output is correct
38 Correct 41 ms 13616 KB Output is correct
39 Correct 39 ms 13712 KB Output is correct
40 Correct 40 ms 13700 KB Output is correct
41 Correct 44 ms 14688 KB Output is correct
42 Correct 42 ms 14716 KB Output is correct
43 Correct 41 ms 14652 KB Output is correct
44 Correct 42 ms 14628 KB Output is correct
45 Correct 45 ms 14620 KB Output is correct
46 Correct 40 ms 14636 KB Output is correct
47 Correct 37 ms 13368 KB Output is correct
48 Correct 42 ms 13352 KB Output is correct
49 Correct 36 ms 13276 KB Output is correct
50 Correct 36 ms 13396 KB Output is correct
51 Correct 35 ms 11868 KB Output is correct
52 Correct 33 ms 11848 KB Output is correct
53 Correct 33 ms 11880 KB Output is correct
54 Correct 37 ms 11796 KB Output is correct
55 Correct 37 ms 12272 KB Output is correct
56 Correct 32 ms 12204 KB Output is correct
57 Correct 44 ms 12264 KB Output is correct
58 Correct 35 ms 12188 KB Output is correct
59 Correct 34 ms 12284 KB Output is correct
60 Correct 37 ms 12228 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 11768 KB Output is correct
2 Correct 42 ms 13512 KB Output is correct
3 Correct 1 ms 1036 KB Output is correct
4 Correct 27 ms 11616 KB Output is correct
5 Correct 42 ms 15784 KB Output is correct
6 Correct 43 ms 15784 KB Output is correct
7 Correct 36 ms 14908 KB Output is correct
8 Correct 34 ms 15272 KB Output is correct
9 Correct 47 ms 16096 KB Output is correct
10 Correct 41 ms 16208 KB Output is correct
11 Correct 49 ms 16236 KB Output is correct
12 Correct 44 ms 16188 KB Output is correct
13 Correct 41 ms 16304 KB Output is correct
14 Correct 43 ms 16252 KB Output is correct
15 Correct 44 ms 16212 KB Output is correct
16 Correct 42 ms 16140 KB Output is correct
17 Correct 41 ms 16016 KB Output is correct
18 Correct 39 ms 15908 KB Output is correct
19 Correct 39 ms 15892 KB Output is correct
20 Correct 39 ms 15976 KB Output is correct
21 Correct 39 ms 16028 KB Output is correct
22 Correct 41 ms 15876 KB Output is correct
23 Correct 33 ms 12200 KB Output is correct
24 Correct 32 ms 12208 KB Output is correct
25 Correct 33 ms 12976 KB Output is correct
26 Correct 37 ms 12908 KB Output is correct
27 Correct 37 ms 14328 KB Output is correct
28 Correct 37 ms 14252 KB Output is correct
29 Correct 37 ms 14448 KB Output is correct
30 Correct 38 ms 14252 KB Output is correct
31 Correct 31 ms 12212 KB Output is correct
32 Correct 32 ms 12272 KB Output is correct
33 Correct 33 ms 12856 KB Output is correct
34 Correct 34 ms 12896 KB Output is correct
35 Correct 37 ms 14076 KB Output is correct
36 Correct 35 ms 14128 KB Output is correct
37 Correct 36 ms 14116 KB Output is correct
38 Correct 39 ms 13968 KB Output is correct
39 Correct 38 ms 14064 KB Output is correct
40 Correct 38 ms 14128 KB Output is correct
41 Correct 39 ms 15052 KB Output is correct
42 Correct 39 ms 14936 KB Output is correct
43 Correct 39 ms 15108 KB Output is correct
44 Correct 39 ms 15128 KB Output is correct
45 Correct 40 ms 15032 KB Output is correct
46 Correct 40 ms 15044 KB Output is correct
47 Correct 36 ms 13788 KB Output is correct
48 Correct 41 ms 13752 KB Output is correct
49 Correct 34 ms 13736 KB Output is correct
50 Correct 36 ms 13884 KB Output is correct
51 Correct 32 ms 12216 KB Output is correct
52 Correct 34 ms 12404 KB Output is correct
53 Correct 35 ms 12464 KB Output is correct
54 Correct 34 ms 12276 KB Output is correct
55 Correct 33 ms 12356 KB Output is correct
56 Correct 33 ms 12416 KB Output is correct
57 Correct 33 ms 12220 KB Output is correct
58 Correct 33 ms 12272 KB Output is correct
59 Correct 33 ms 12268 KB Output is correct
60 Correct 33 ms 12172 KB Output is correct