QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#356972#6335. Belt Conveyorzyz0725 365ms33000kbC++172.6kb2024-03-18 16:50:282024-03-18 16:50:28

Judging History

你现在查看的是最新测评结果

  • [2024-03-18 16:50:28]
  • 评测
  • 测评结果:25
  • 用时:365ms
  • 内存:33000kb
  • [2024-03-18 16:50:28]
  • 提交

answer

#include "conveyor.h"
#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);--Ti)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
using ll=long long;
const int N=1e5+5;
vector<pair<int,int>> e[N];
int vis[N],fa[N],fai[N];
void dfs(int u){
	for(auto [v,i]:e[u]){
		if(v!=fa[u]){
			fa[v]=u;
			fai[v]=i;
			dfs(v);
		}
	}
}
void Solve(int n,vector<int> U,vector<int> V){
	For(i,0,n-2){
		e[U[i]+1].emplace_back(V[i]+1,i+1);
		e[V[i]+1].emplace_back(U[i]+1,-i-1);
	}
	vector<int> initx(n-1),ans(n-1);
	auto assign=[&](int u,bool to){
		ans[abs(fai[u])-1]=(fai[u]>0)^to;
	};
	while(1){
		vector<int> leaf;
		int rt=0;
		For(u,1,n){
			if(vis[u]) continue;
			e[u].erase(remove_if(range(e[u]),[](pair<int,int> x){
				return vis[x.first];
			}),e[u].end());
			if(e[u].size()==1){
				leaf.push_back(u);
			}else if(e[u].size()>2){
				rt=u;
			}
		}
		if(leaf.size()<2) break;
		vector<vector<int>> chains;
		if(leaf.size()==2){
			dfs(leaf[1]);
			vector<int> pth;
			int v;
			for(v=leaf[0];v!=leaf[1];v=fa[v]){
				vis[v]=1;
				pth.push_back(v);
			}
			pth.push_back(v);
			reverse(range(pth));
			chains={pth};
		}else{
			fa[rt]=0;
			dfs(rt);
			for(int u:leaf){
				vector<int> pth;
				int v;
				for(v=u;e[v].size()<=2;v=fa[v]){
					vis[v]=1;
					pth.push_back(v);
				}
				pth.push_back(v);
				reverse(range(pth));
				chains.push_back(pth);
			}
		}
		vector<int> vec_x(initx),vec_y(n);
		for(const auto& pth:chains){
			for(int i=1;i<int(pth.size());i+=2){
				vec_y[pth[i]-1]=1;
			}
		}
		auto res=Query(vec_x,vec_y);
		for(const auto& pth:chains){
			For(i,1,int(pth.size())-1){
				vec_x[abs(fai[pth[i]])-1]=1;
			}
		}
		auto res2=Query(vec_x,vec_y);
		for(const auto& pth:chains){
			int s=pth.size()-1;
			s-=!(s%2);
			for(int i=s,pre_to=0;i>0;i-=2){
				int u=pth[i];
				if(res[u-1]){
					assign(u,1);
					if(i+1<int(pth.size())){
						assign(pth[i+1],0);
					}
					pre_to=1;
				}else if(res2[u-1]){
					assign(u,0);
					if(i+1<int(pth.size())){
						assign(pth[i+1],1);
					}
					pre_to=0;
				}else if(pre_to){
					bool to=res[pth[i+1]-1];
					assign(u,to);
					assign(pth[i+1],to);
					pre_to=to;
				}else{
					bool to=!res2[pth[i+1]-1];
					assign(u,to);
					assign(pth[i+1],to);
					pre_to=to;
				}
				if(pre_to){
					initx[abs(fai[u])-1]=1;
				}
			}
		}
	}
	Answer(ans);
}
#ifdef LOCAL
#include "grader.cpp"
#endif

詳細信息

Subtask #1:

score: 1
Accepted

Test #1:

score: 1
Accepted
time: 1ms
memory: 6716kb

input:

random1
2
0
1
1
0xC321A02965AC2640

output:

Accepted: 2

result:

ok correct

Test #2:

score: 0
Accepted
time: 1ms
memory: 6312kb

input:

random1
2
1
0
0
0x8A99AD9552B2C218

output:

Accepted: 2

result:

ok correct

Test #3:

score: 0
Accepted
time: 2ms
memory: 6424kb

input:

random1
2
1
0
1
0x024D21FA307D148D

output:

Accepted: 2

result:

ok correct

Test #4:

score: 0
Accepted
time: 2ms
memory: 6920kb

input:

random1
2
0
1
0
0x3C96AB23CEB63F75

output:

Accepted: 2

result:

ok correct

Subtask #2:

score: 14
Accepted

Dependency #1:

100%
Accepted

Test #5:

score: 14
Accepted
time: 1ms
memory: 6916kb

input:

priority
30
10 29 10 13 17 11 2 15 15 27 9 26 18 0 14 1 22 24 29 28 6 22 4 20 15 5 28 4 21
24 3 13 1 8 13 12 8 19 16 3 1 10 24 29 12 8 4 7 2 7 28 25 12 7 2 23 27 22
89058848 6377689 24189123 31671827 205117644 254374430 56016068 6819602 212866321 246625321 274047319 230485311 202854776 280075001 203...

output:

Accepted: 4

result:

ok correct

Test #6:

score: 0
Accepted
time: 0ms
memory: 6152kb

input:

random1
30
18 20 12 0 13 2 9 11 24 7 15 26 17 19 23 10 20 16 3 11 24 1 18 19 1 28 22 6 6
26 21 5 27 27 14 15 8 0 17 5 16 3 10 29 13 14 25 28 25 23 8 9 4 2 4 12 7 22
1 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 0 1
0x139BEEDAC0AE4AFB

output:

Accepted: 2

result:

ok correct

Test #7:

score: 0
Accepted
time: 0ms
memory: 6436kb

input:

priority
30
15 20 29 0 10 9 28 26 23 6 19 20 8 13 27 27 1 7 16 26 10 4 16 1 18 8 5 14 13
9 22 15 24 29 2 3 19 2 3 17 0 7 14 12 5 6 25 18 25 24 11 4 12 23 11 17 21 28
155983625 867841392 695948077 619352269 127722564 849426565 618649370 326405673 698896139 727112455 131828530 787535071 635627968 4725...

output:

Accepted: 2

result:

ok correct

Test #8:

score: 0
Accepted
time: 0ms
memory: 6584kb

input:

random1
30
11 11 11 11 23 20 11 11 11 26 11 21 11 11 11 27 11 11 11 16 13 17 5 11 11 1 11 14 11
24 28 10 3 11 11 22 25 8 11 29 11 12 15 9 11 19 0 2 11 11 11 11 18 4 11 7 11 6
0 1 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1
0xD66348F4E914D783

output:

Accepted: 2

result:

ok correct

Test #9:

score: 0
Accepted
time: 1ms
memory: 6144kb

input:

priority
30
1 7 19 19 21 3 16 25 19 2 4 19 19 22 19 19 27 18 19 24 19 19 19 19 19 19 19 19 28
19 19 29 0 19 19 19 19 15 19 19 10 5 19 6 14 19 19 23 19 8 11 9 26 17 12 13 20 19
175687064 613757478 145110402 817656856 712251185 850089290 510909115 900701092 956086121 136191567 90104148 72809899 345506...

output:

Accepted: 2

result:

ok correct

Test #10:

score: 0
Accepted
time: 2ms
memory: 7120kb

input:

priority
30
22 22 22 16 13 1 13 22 15 6 21 22 2 23 27 22 4 13 3 13 26 5 13 22 9 8 11 25 13
0 14 13 13 29 13 7 18 22 22 13 28 22 13 22 12 22 20 22 24 13 13 10 17 13 22 22 13 19
205508605 212446816 92507839 281454564 232828716 252753556 236784221 262865505 235145960 298570090 277536286 225110287 21565...

output:

Accepted: 4

result:

ok correct

Subtask #3:

score: 10
Accepted

Test #11:

score: 10
Accepted
time: 45ms
memory: 31456kb

input:

random1
100000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...

output:

Accepted: 2

result:

ok correct

Test #12:

score: 0
Accepted
time: 42ms
memory: 31308kb

input:

priority
100000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 ...

output:

Accepted: 2

result:

ok correct

Test #13:

score: 0
Accepted
time: 45ms
memory: 33000kb

input:

random1
100000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...

output:

Accepted: 2

result:

ok correct

Test #14:

score: 0
Accepted
time: 49ms
memory: 31484kb

input:

priority
100000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 ...

output:

Accepted: 2

result:

ok correct

Subtask #4:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #15:

score: 75
Accepted
time: 365ms
memory: 27604kb

input:

random1
100000
80421 79656 7373 22779 46143 23525 47891 79913 37297 20998 75128 48153 63344 14542 7176 46311 14404 86722 64420 35721 9418 16518 68787 60231 62713 24600 3621 36142 16253 35726 59248 8570 29713 29710 65003 65386 98313 32539 48464 79006 7464 99396 45447 11929 44648 44081 94041 40159 307...

output:

Accepted: 22

result:

ok correct

Test #16:

score: 0
Accepted
time: 319ms
memory: 27696kb

input:

random1
100000
47543 22001 16105 85619 83739 65453 81631 39199 45451 20382 85595 14410 39199 30963 55201 76378 25120 7516 39199 54202 40278 55022 44298 24421 18026 66509 33880 81569 24498 99677 49879 5902 76830 19128 34499 73731 32890 52171 54572 39199 91782 49370 45817 61462 23515 15408 40298 74640...

output:

Accepted: 18

result:

ok correct

Test #17:

score: -75
Time Limit Exceeded

input:

random1
100000
54154 40864 51853 60873 46781 94584 40170 53625 38806 77573 2040 39786 34858 81565 80712 35628 88600 17657 29042 78470 12465 42107 99871 96640 83887 26160 67221 77210 16548 76907 36070 44287 83854 17095 84838 80345 84838 81932 77302 34933 63457 76048 85028 48884 95405 88687 84838 3426...

output:

Unauthorized output

result: