oj.uz

Submission #928645

# Submission time Handle Problem Language Result Execution time Memory
928645 2024-02-17T00:21:41 Z MilosMilutinovic Stray Cat (JOI20_stray) C++14
15 / 100
 34 ms 16616 KB 
#include "Anthony.h"
#include<bits/stdc++.h>
 
using namespace std;
 
namespace {
const int seq[]={1,0,1,1,0,0};
int n,tot;
int v[40005],nxt[40005],h[20005],d[20005],q[20005],idx[20005];
vector<int> ret;
 
void addedge(int x,int y){
	v[++tot]=y; nxt[tot]=h[x]; h[x]=tot;
	v[++tot]=x; nxt[tot]=h[y]; h[y]=tot;
}
 
void bfs(){
	for(int i=0;i<n;i++) d[i]=-1;
	int front=0,rear=0;
	q[rear++]=0; d[0]=0;
	while(front<rear){
		int x=q[front];
		for(int p=h[x];p;p=nxt[p]){
			if(d[v[p]]==-1){
				d[v[p]]=d[x]+1;
				q[rear++]=v[p];
			}
		}
		++front;
	}
}

void dfs(int x,int fa,int lst,int i){
	int ch=0;
	for(int p=h[x];p;p=nxt[p]) if(v[p]!=fa) ch++;
	if(ch==0) return;
	if(ch==1){
		for(int p=h[x];p;p=nxt[p]){
			if(v[p]==fa) continue;
			ret[idx[v[p]]]=(lst^seq[i]);
			dfs(v[p],x,lst,(i+1)%6);
		}
	}else{
		for(int p=h[x];p;p=nxt[p]){
			if(v[p]==fa) continue;
			ret[idx[v[p]]]=(x==0?0:ret[idx[x]])^1;
			dfs(v[p],x,x==0?0:ret[idx[x]],1);
		}
	}
}
}
 
vector<int> Mark(int n,int m,int a,int b,vector<int> u,vector<int> v){
	::n=n;
	for(int i=0;i<m;i++) addedge(u[i],v[i]);
	if(a>=3){
		bfs();
		vector<int> col(m);
		for(int i=0;i<m;i++) col[i]=min(d[u[i]],d[v[i]])%3;
		return col;
	}else{
		for(int i=0;i<m;i++){
			if(d[u[i]]>d[v[i]]) swap(u[i],v[i]);
			idx[v[i]]=i;
		}
		ret.resize(m);
		dfs(0,0,0,0);
	}
	return vector<int>(m,0);
}
#include "Catherine.h"
#include<bits/stdc++.h>

#define pb push_back
 
using namespace std;
 
namespace {
 
int a,b;
bool up;
vector<int> edg;
}  // namespace
 
void Init(int A,int B){
	a=A; b=B;
	up=false;
}
 
int Move(vector<int> y){
	if(a>=3){
		int cnt=0;
		for(int i=0;i<a;i++) cnt+=(y[i]>0?1:0);
		if(cnt==1){
			for(int i=0;i<a;i++) if(y[i]>0) return i;
		}
		for(int i=0;i<a;i++){
			if(y[i]>0&&y[(i+1)%3]>0) return i;
		}
	}
	if(up){
		if(y[0]==0){
			edg.pb(1);
			return 1;
		}
		if(y[1]==0){
			edg.pb(0);
			return 0;
		}
		edg.pb(edg.back()^1);
		return edg.back()^1;
	}
	if(y[0]==0&&y[1]==0){
		up=true;
		edg.pb(edg.back());
		return -1;
	}
	if(y[0]==0){
		edg.pb(1);
		return 1;
	}
	edg.pb(0);
	return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 15356 KB Output is correct
2 Correct 1 ms 788 KB Output is correct
3 Correct 27 ms 14620 KB Output is correct
4 Correct 32 ms 16616 KB Output is correct
5 Correct 31 ms 16436 KB Output is correct
6 Correct 26 ms 15124 KB Output is correct
7 Correct 24 ms 15184 KB Output is correct
8 Correct 28 ms 15792 KB Output is correct
9 Correct 30 ms 15920 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 15356 KB Output is correct
2 Correct 1 ms 788 KB Output is correct
3 Correct 27 ms 14620 KB Output is correct
4 Correct 32 ms 16616 KB Output is correct
5 Correct 31 ms 16436 KB Output is correct
6 Correct 26 ms 15124 KB Output is correct
7 Correct 24 ms 15184 KB Output is correct
8 Correct 28 ms 15792 KB Output is correct
9 Correct 30 ms 15920 KB Output is correct
10 Correct 25 ms 13624 KB Output is correct
11 Correct 23 ms 13220 KB Output is correct
12 Correct 27 ms 13200 KB Output is correct
13 Correct 24 ms 13360 KB Output is correct
14 Correct 24 ms 13664 KB Output is correct
15 Correct 27 ms 13904 KB Output is correct
16 Correct 28 ms 15924 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 12876 KB Output is correct
2 Correct 0 ms 800 KB Output is correct
3 Correct 21 ms 12272 KB Output is correct
4 Correct 31 ms 14420 KB Output is correct
5 Correct 28 ms 14408 KB Output is correct
6 Correct 26 ms 12844 KB Output is correct
7 Correct 24 ms 13060 KB Output is correct
8 Correct 27 ms 13636 KB Output is correct
9 Correct 28 ms 13652 KB Output is correct
10 Correct 26 ms 13424 KB Output is correct
11 Correct 27 ms 13332 KB Output is correct
12 Correct 26 ms 13388 KB Output is correct
13 Correct 34 ms 13400 KB Output is correct
14 Correct 32 ms 13696 KB Output is correct
15 Correct 27 ms 13648 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 12876 KB Output is correct
2 Correct 0 ms 800 KB Output is correct
3 Correct 21 ms 12272 KB Output is correct
4 Correct 31 ms 14420 KB Output is correct
5 Correct 28 ms 14408 KB Output is correct
6 Correct 26 ms 12844 KB Output is correct
7 Correct 24 ms 13060 KB Output is correct
8 Correct 27 ms 13636 KB Output is correct
9 Correct 28 ms 13652 KB Output is correct
10 Correct 26 ms 13424 KB Output is correct
11 Correct 27 ms 13332 KB Output is correct
12 Correct 26 ms 13388 KB Output is correct
13 Correct 34 ms 13400 KB Output is correct
14 Correct 32 ms 13696 KB Output is correct
15 Correct 27 ms 13648 KB Output is correct
16 Correct 21 ms 11336 KB Output is correct
17 Correct 23 ms 11336 KB Output is correct
18 Correct 26 ms 11464 KB Output is correct
19 Correct 23 ms 11344 KB Output is correct
20 Correct 24 ms 11960 KB Output is correct
21 Correct 31 ms 11656 KB Output is correct
22 Correct 28 ms 13828 KB Output is correct
23 Correct 25 ms 11380 KB Output is correct
24 Correct 23 ms 11596 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1052 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 10640 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 10648 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -