oj.uz

Submission #939601

# Submission time Handle Problem Language Result Execution time Memory
939601 2024-03-06T14:55:27 Z pcc Stray Cat (JOI20_stray) C++14
91 / 100
 42 ms 16888 KB 
#include "Anthony.h"
#include <vector>
#include <bits/stdc++.h>


namespace ANTHONY{

#define pii pair<int,int>
#define fs first
#define sc second
	using namespace std;
	const int mxn = 2e4+10;
	int N,M;
	vector<pii> paths[mxn];
	vector<pii> edges;

	namespace S1{
		queue<int> q;
		int dist[mxn];
		void BFS(){
			memset(dist,-1,sizeof(dist));
			dist[0] = 0;
			q.push(0);
			while(!q.empty()){
				auto now = q.front();
				q.pop();
				for(auto nxt:paths[now]){
					if(dist[nxt.fs] == -1)dist[nxt.fs] = dist[now]+1,q.push(nxt.fs);
				}
			}
			return;
		}
		vector<int> GO(){
			//cout<<"CASE 1"<<endl;
			vector<int> ans(M,0);
			BFS();
			for(int i = 0;i<M;i++){
				auto [a,b] = edges[i];
				if(dist[a]>dist[b])swap(a,b);
				if(dist[a]==dist[b])ans[i] = (dist[a]+1)%3;
				else ans[i] = dist[b]%3;
				//cout<<a<<' '<<b<<" "<<ans[i]<<endl;
			}
			//for(int i = 0;i<N;i++)cout<<dist[i]<<' ';cout<<endl;
			//cout<<ans.size()<<endl;
			//for(auto &i:ans)cout<<i;cout<<endl;
			return ans;
		}
	}

	namespace S2{
		string bin = "100110";//11:0,12:1
		vector<int> ans;
		void dfs(int now,int fa,int pt){
			for(auto nxt:paths[now]){
				if(nxt.fs == fa)continue;
				if(paths[nxt.fs].size() != 2){
					if(pt>10){
						ans[nxt.sc] = (pt==11?0:1);
						dfs(nxt.fs,now,(pt==11?12:11));
					}
					else{
						if(bin[pt]=='0'){
							ans[nxt.sc] = 0;
							dfs(nxt.fs,now,12);
						}
						else{
							ans[nxt.sc] = 1;
							dfs(nxt.fs,now,11);
						}
					}
				}
				else{
					if(pt==11){
						ans[nxt.sc] = 0;
						dfs(nxt.fs,now,0);
					}
					else if(pt == 12){
						ans[nxt.sc] = 1;
						dfs(nxt.fs,now,1);
					}
					else{
						ans[nxt.sc] = bin[pt]-'0';
						dfs(nxt.fs,now,(pt+1)%bin.size());
					}
				}
			}
			return;
		}
		vector<int> GO(){
			ans.resize(M);
			dfs(0,0,11);
			for(int i = 0;i<M;i++){
				//cout<<edges[i].fs<<' '<<edges[i].sc<<" "<<ans[i]<<endl;
			}
			return ans;
		}
	}

	vector<int> SOLVE(int n,int m,int a,int b,vector<int> va,vector<int> vb){
		N = n,M = m;
		for(int i = 0;i<m;i++){
			edges.push_back({va[i],vb[i]});
			paths[va[i]].push_back({vb[i],i});
			paths[vb[i]].push_back({va[i],i});
		}
		if(a>=3)return S1::GO();
		else return S2::GO();
	}
}  // namespace

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
  return ANTHONY::SOLVE(N,M,A,B,U,V);
}

#include "Catherine.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second

namespace NEKO{

int task;
vector<int> route;
int turn;

}  // namespace

void Init(int A, int B) {
	NEKO::task = (A<=2);
	NEKO::turn = 3;
	return;
}

namespace S1{
	int GO(vector<int> v){
		int sum = 0;
		for(auto &i:v)sum += (i?1:0);
		if(sum == 1)return max_element(v.begin(),v.end())-v.begin();
		int s = 0;
		for(int i = 0;i<3;i++){
			if(v[i])s ^= i;
		}
		switch(s){
			case 1:
				return 0;
			case 2:
				return 2;
			case 3:
				return 1;
		}
		assert(false);
		return -1;
	}
}

namespace S2{
	int pre = -1;
	int nt = -1;
	int C0(vector<int> v){
		//cout<<"C0"<<endl;
		int s = 0;
		for(auto &i:v)s += (i!=0);
		if(s == 1){
			return (pre = max_element(v.begin(),v.end())-v.begin());
		}
		else if(s == 0)return -1;
		else return (pre ^= 1);
	}
	int C1(vector<int> v){
		//cout<<"C1"<<endl;
		nt = 0;
		for(int i = 0;i<2;i++){
			if(v[i] == 1)return (pre = i);
		}
		assert(false);
	}
	int C2(vector<int> v){
		//cout<<"C2"<<endl;
		int s = (v[0]?0:1);
		NEKO::turn--;
		if(pre == -1){
			NEKO::route.push_back((v[0]?0:1));
			if(v[1])s = 1;
			else s = 0;
			NEKO::route.push_back(s);
			return (pre = s);
		}
		else if(NEKO::turn>=0){
			NEKO::route.push_back(s);
			return (pre = s);
		}
		else if(NEKO::turn == -1){
			NEKO::route.push_back(s);
			return -1;
		}
		else if(NEKO::turn >= -3){
			return (pre = s);
		}
		string ss;
		for(auto &i:NEKO::route){
			ss += '0'+i;
		}
		//cout<<ss<<endl;
		string t = "100110100110100110";
		bool flag = false;
		for(int i = 0;i+ss.size()<=t.size();i++){
			if(t.substr(i,ss.size()) == ss)flag = true;
		}
		nt = 0;
		if(flag)return s;
		else return -1;
	}
	int GO(vector<int> v){
		int re = -2;
		if(!nt)re = C0(v);
		int s = 0;
		for(auto &i:v)s +=i;
		if(re == -2&&s + (pre>=0) != 2){
			if(pre == -1){
				nt = 0;
				re = C0(v);
			}
			else{
				nt = 0;
				if(v[pre] == 0)re = -1;
				else re = (pre ^= 1);
			}
		}
		if(re == -2)re = C2(v);
		//for(auto &i:v)//cout<<i<<' ';cout<<s<<","<<pre<<":"<<re<<endl;
		return re;
	}
}

int Move(std::vector<int> y) {
	if(NEKO::task)return S2::GO(y);
	else return S1::GO(y);
}

Compilation message

Anthony.cpp: In function 'std::vector<int> ANTHONY::S1::GO()':
Anthony.cpp:38:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |     auto [a,b] = edges[i];
      |          ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 15856 KB Output is correct
2 Correct 1 ms 1296 KB Output is correct
3 Correct 25 ms 15508 KB Output is correct
4 Correct 37 ms 16888 KB Output is correct
5 Correct 35 ms 16888 KB Output is correct
6 Correct 28 ms 15760 KB Output is correct
7 Correct 28 ms 15740 KB Output is correct
8 Correct 39 ms 16452 KB Output is correct
9 Correct 34 ms 16340 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 15856 KB Output is correct
2 Correct 1 ms 1296 KB Output is correct
3 Correct 25 ms 15508 KB Output is correct
4 Correct 37 ms 16888 KB Output is correct
5 Correct 35 ms 16888 KB Output is correct
6 Correct 28 ms 15760 KB Output is correct
7 Correct 28 ms 15740 KB Output is correct
8 Correct 39 ms 16452 KB Output is correct
9 Correct 34 ms 16340 KB Output is correct
10 Correct 26 ms 13808 KB Output is correct
11 Correct 34 ms 13768 KB Output is correct
12 Correct 31 ms 13828 KB Output is correct
13 Correct 28 ms 13736 KB Output is correct
14 Correct 27 ms 13984 KB Output is correct
15 Correct 32 ms 14328 KB Output is correct
16 Correct 32 ms 16384 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13580 KB Output is correct
2 Correct 1 ms 1308 KB Output is correct
3 Correct 24 ms 13016 KB Output is correct
4 Correct 33 ms 14840 KB Output is correct
5 Correct 39 ms 14804 KB Output is correct
6 Correct 28 ms 13512 KB Output is correct
7 Correct 27 ms 13576 KB Output is correct
8 Correct 31 ms 14088 KB Output is correct
9 Correct 30 ms 14036 KB Output is correct
10 Correct 30 ms 13808 KB Output is correct
11 Correct 28 ms 13812 KB Output is correct
12 Correct 31 ms 13892 KB Output is correct
13 Correct 28 ms 13832 KB Output is correct
14 Correct 32 ms 14080 KB Output is correct
15 Correct 32 ms 14072 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13580 KB Output is correct
2 Correct 1 ms 1308 KB Output is correct
3 Correct 24 ms 13016 KB Output is correct
4 Correct 33 ms 14840 KB Output is correct
5 Correct 39 ms 14804 KB Output is correct
6 Correct 28 ms 13512 KB Output is correct
7 Correct 27 ms 13576 KB Output is correct
8 Correct 31 ms 14088 KB Output is correct
9 Correct 30 ms 14036 KB Output is correct
10 Correct 30 ms 13808 KB Output is correct
11 Correct 28 ms 13812 KB Output is correct
12 Correct 31 ms 13892 KB Output is correct
13 Correct 28 ms 13832 KB Output is correct
14 Correct 32 ms 14080 KB Output is correct
15 Correct 32 ms 14072 KB Output is correct
16 Correct 27 ms 12032 KB Output is correct
17 Correct 24 ms 12036 KB Output is correct
18 Correct 26 ms 11772 KB Output is correct
19 Correct 25 ms 11948 KB Output is correct
20 Correct 28 ms 12460 KB Output is correct
21 Correct 27 ms 12204 KB Output is correct
22 Correct 37 ms 14300 KB Output is correct
23 Correct 25 ms 12032 KB Output is correct
24 Correct 25 ms 12032 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1564 KB Output is correct
2 Correct 1 ms 1304 KB Output is correct
3 Correct 2 ms 1560 KB Output is correct
4 Correct 2 ms 1568 KB Output is correct
5 Correct 2 ms 1560 KB Output is correct
6 Correct 2 ms 1564 KB Output is correct
7 Correct 2 ms 1552 KB Output is correct
8 Correct 2 ms 1564 KB Output is correct
9 Correct 2 ms 1560 KB Output is correct
10 Correct 2 ms 1628 KB Output is correct
11 Correct 2 ms 1572 KB Output is correct
12 Correct 1 ms 1564 KB Output is correct
13 Correct 2 ms 1464 KB Output is correct
14 Correct 2 ms 1568 KB Output is correct
15 Correct 2 ms 1564 KB Output is correct
16 Correct 2 ms 1564 KB Output is correct
17 Correct 2 ms 1556 KB Output is correct
18 Correct 2 ms 1564 KB Output is correct
19 Correct 2 ms 1572 KB Output is correct
20 Correct 2 ms 1572 KB Output is correct
21 Correct 2 ms 1572 KB Output is correct
22 Correct 1 ms 1564 KB Output is correct
23 Correct 1 ms 1576 KB Output is correct
24 Correct 2 ms 1572 KB Output is correct
25 Correct 2 ms 1556 KB Output is correct
26 Correct 2 ms 2072 KB Output is correct
27 Correct 2 ms 1564 KB Output is correct
28 Correct 2 ms 1556 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 11752 KB Output is correct
2 Correct 27 ms 13064 KB Output is correct
3 Correct 1 ms 1296 KB Output is correct
4 Correct 23 ms 12020 KB Output is correct
5 Correct 34 ms 14988 KB Output is correct
6 Correct 38 ms 15348 KB Output is correct
7 Correct 28 ms 14012 KB Output is correct
8 Correct 31 ms 14048 KB Output is correct
9 Correct 36 ms 15112 KB Output is correct
10 Correct 33 ms 15060 KB Output is correct
11 Correct 31 ms 15040 KB Output is correct
12 Correct 31 ms 15060 KB Output is correct
13 Correct 42 ms 15388 KB Output is correct
14 Correct 32 ms 15076 KB Output is correct
15 Correct 31 ms 15072 KB Output is correct
16 Correct 32 ms 15128 KB Output is correct
17 Correct 31 ms 14792 KB Output is correct
18 Correct 28 ms 14812 KB Output is correct
19 Correct 32 ms 14812 KB Output is correct
20 Correct 30 ms 14728 KB Output is correct
21 Correct 31 ms 14932 KB Output is correct
22 Correct 31 ms 14716 KB Output is correct
23 Correct 25 ms 12260 KB Output is correct
24 Correct 24 ms 12244 KB Output is correct
25 Correct 26 ms 12760 KB Output is correct
26 Correct 26 ms 13008 KB Output is correct
27 Correct 28 ms 13664 KB Output is correct
28 Correct 28 ms 13632 KB Output is correct
29 Correct 30 ms 13536 KB Output is correct
30 Correct 28 ms 13484 KB Output is correct
31 Correct 26 ms 12256 KB Output is correct
32 Correct 25 ms 12152 KB Output is correct
33 Correct 27 ms 12572 KB Output is correct
34 Correct 26 ms 12740 KB Output is correct
35 Correct 27 ms 13400 KB Output is correct
36 Correct 30 ms 13400 KB Output is correct
37 Correct 28 ms 13420 KB Output is correct
38 Correct 27 ms 13348 KB Output is correct
39 Correct 27 ms 13396 KB Output is correct
40 Correct 28 ms 13412 KB Output is correct
41 Correct 30 ms 14116 KB Output is correct
42 Correct 28 ms 14044 KB Output is correct
43 Correct 28 ms 14304 KB Output is correct
44 Correct 28 ms 14036 KB Output is correct
45 Correct 31 ms 14048 KB Output is correct
46 Correct 37 ms 14104 KB Output is correct
47 Correct 31 ms 13384 KB Output is correct
48 Correct 27 ms 13304 KB Output is correct
49 Correct 27 ms 13216 KB Output is correct
50 Correct 27 ms 13828 KB Output is correct
51 Correct 25 ms 12416 KB Output is correct
52 Correct 28 ms 12320 KB Output is correct
53 Correct 26 ms 12236 KB Output is correct
54 Correct 26 ms 12248 KB Output is correct
55 Correct 25 ms 12384 KB Output is correct
56 Correct 28 ms 12268 KB Output is correct
57 Correct 26 ms 12260 KB Output is correct
58 Correct 26 ms 12244 KB Output is correct
59 Correct 26 ms 12252 KB Output is correct
60 Correct 26 ms 12248 KB Output is correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11776 KB Output is correct
2 Correct 28 ms 13172 KB Output is correct
3 Correct 1 ms 1312 KB Output is correct
4 Correct 22 ms 11964 KB Output is correct
5 Correct 33 ms 15060 KB Output is correct
6 Correct 34 ms 15020 KB Output is correct
7 Correct 28 ms 14044 KB Output is correct
8 Correct 27 ms 14016 KB Output is correct
9 Correct 32 ms 15028 KB Output is correct
10 Correct 36 ms 15016 KB Output is correct
11 Correct 35 ms 15024 KB Output is correct
12 Correct 33 ms 15060 KB Output is correct
13 Correct 32 ms 15084 KB Output is correct
14 Correct 32 ms 15072 KB Output is correct
15 Correct 32 ms 15064 KB Output is correct
16 Correct 34 ms 14968 KB Output is correct
17 Correct 30 ms 14808 KB Output is correct
18 Correct 31 ms 14776 KB Output is correct
19 Correct 35 ms 14712 KB Output is correct
20 Correct 32 ms 14812 KB Output is correct
21 Correct 32 ms 14784 KB Output is correct
22 Correct 31 ms 14788 KB Output is correct
23 Correct 25 ms 12216 KB Output is correct
24 Correct 25 ms 12248 KB Output is correct
25 Correct 27 ms 12656 KB Output is correct
26 Correct 26 ms 12760 KB Output is correct
27 Correct 28 ms 13436 KB Output is correct
28 Correct 30 ms 13532 KB Output is correct
29 Correct 28 ms 14040 KB Output is correct
30 Correct 28 ms 13608 KB Output is correct
31 Correct 25 ms 12224 KB Output is correct
32 Correct 25 ms 12260 KB Output is correct
33 Correct 26 ms 12828 KB Output is correct
34 Correct 28 ms 12824 KB Output is correct
35 Correct 31 ms 13524 KB Output is correct
36 Correct 27 ms 13460 KB Output is correct
37 Correct 27 ms 13540 KB Output is correct
38 Correct 28 ms 13520 KB Output is correct
39 Correct 28 ms 13528 KB Output is correct
40 Correct 32 ms 13532 KB Output is correct
41 Correct 38 ms 14204 KB Output is correct
42 Correct 34 ms 14000 KB Output is correct
43 Correct 30 ms 14036 KB Output is correct
44 Correct 28 ms 14012 KB Output is correct
45 Correct 35 ms 14008 KB Output is correct
46 Correct 33 ms 14044 KB Output is correct
47 Correct 28 ms 13664 KB Output is correct
48 Correct 27 ms 13268 KB Output is correct
49 Correct 27 ms 13144 KB Output is correct
50 Correct 27 ms 13396 KB Output is correct
51 Correct 26 ms 12252 KB Output is correct
52 Correct 25 ms 12252 KB Output is correct
53 Correct 29 ms 12396 KB Output is correct
54 Incorrect 24 ms 12252 KB Wrong Answer [6]
55 Halted 0 ms 0 KB -