QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#245667	#7769. Axium Crisis	zyz07	55	3541ms	3556kb	C++17	2.7kb	2023-11-10 09:19:40	2023-11-10 09:19:40

Judging History

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

[2023-11-10 09:19:40]
评测

测评结果：55
用时：3541ms
内存：3556kb

查看

[2023-11-10 09:19:40]
提交

answer

#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;
mt19937 eng(random_device{}());
const int N=19;
int T,tid,n,a[N],val[N],vis[N];
vector<pair<int,int>> e[N];
struct Trie{
	int ch[N][2],tot;
}trie;
struct Answer{
	int tot;
	vector<int> val;
	vector<pair<int,int>> path;
}ans,cur;
void dfs(int,bool);
bool flg;
void get_path(int8_t u,int8_t v,int8_t fa,int8_t v_,bool ok,bool fir_){
	if(fa&&e[v].size()==1&&ok){
		cur.path.emplace_back(u,v);
		int pre=cur.tot;
		cur.tot=trie.tot;
		dfs(n>11?u+1:u,fir_);
		cur.tot=pre;
		cur.path.pop_back();
	}
	for(auto [x,i]:e[v]){
		if(x!=fa&&!vis[i]){
			vis[i]=1;
			int dst=eng()%2;
			For(y,0,1){
				if((val[i]!=2&&y!=val[i])||(val[i]==2&&!fir_&&y!=dst)){
					continue;
				}
				int pre=val[i];
				val[i]=y;
				int& nxt=trie.ch[v_][val[i]],ok_=0;
				if(!nxt){
					nxt=++trie.tot;
					ok_=1;
				}
				get_path(u,x,v,nxt,ok_,fir_&&(pre!=2||(n<=11&&!flg)));
				if(ok_){
					nxt=0;
					--trie.tot;
				}
				val[i]=pre;
			}
			vis[i]=0;
		}
	}
}
void dfs(int u,bool fir){
	if(u==n+1){
		if(cur.tot>ans.tot){
			cur.val.resize(n-1);
			For(i,0,n-2){
				cur.val[i]=val[i+1]!=2?val[i+1]:0;
			}
			ans=cur;
		}
		return;
	}
	if(count(vis+1,vis+n,0)+cur.tot<=ans.tot){
		return;
	}
	Trie pret=trie;
	dfs(u+1,fir);
	trie=pret;
	get_path(u,u,0,0,0,fir);
}
namespace zero{
	void dfs(int u,int fa,int d,int& x,int& xd){
		if(d>xd){
			x=u;
			xd=d;
		}
		for(auto [v,i]:e[u]){
			if(v!=fa){
				dfs(v,u,d+1,x,xd);
			}
		}
	}
	tuple<int,int,int> diam(){
		int x=0,xd=-1,y=0,yd=-1;
		dfs(1,0,0,x,xd);
		dfs(x,0,0,y,yd);
		return {x,y,yd};
	}
	void solve(){
		auto [u,v,d]=diam();
		cout<<d+1<<'\n';
		cout<<"1\n";
		For(i,1,n-1) cout<<0<<" \n"[i==n-1];
		cout<<u-1<<' '<<v-1<<'\n';
		For(i,1,n) e[i].clear();
	}
}
int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	// assert(freopen("B.in","r",stdin));
	// assert(freopen("B.out","w",stdout));
	cin>>T>>tid;
	cout<<"1\n";
	while(T--){
		cin>>n;
		For(i,1,n-1){
			int u,v;
			cin>>u>>v>>val[i];
			++u;
			++v;
			e[u].emplace_back(v,i);
			e[v].emplace_back(u,i);
		}
		if(count(val+1,val+n,0)==n-1){
			zero::solve();
			continue;
		}
		flg=count(val+1,val+n,2)==n-1;
		For(i,0,flg||n<=11?0:3) dfs(1,1);
		cout<<ans.tot+1<<'\n';
		cout<<ans.path.size()<<'\n';
		for(int x:ans.val){
			cout<<x<<' ';
		}
		cout<<'\n';
		for(auto [u,v]:ans.path){
			cout<<u-1<<' '<<v-1<<'\n';
		}
		ans.tot=0;
		For(i,1,n) e[i].clear();
	}
	return 0;
}

源文件, 语言: C++17

详细

Subtask #1:

score: 10

Accepted

Test #1:

score: 10

Accepted

time: 0ms

memory: 3488kb

input:

output:

result:

ok Accepted. Good Job!

Test #2:

score: 10

Accepted

time: 2ms

memory: 3504kb

input:

output:

result:

ok Accepted. Good Job!

Subtask #2:

score: 10

Accepted

Test #3:

score: 10

Accepted

time: 6ms

memory: 3484kb

input:

output:

result:

ok Accepted. Good Job!

Test #4:

score: 10

Accepted

time: 6ms

memory: 3424kb

input:

output:

result:

ok Accepted. Good Job!

Subtask #3:

score: 0

Wrong Answer

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Test #5:

score: 10

Accepted

time: 87ms

memory: 3420kb

input:

output:

result:

ok Accepted. Good Job!

Test #6:

score: 0

Wrong Answer

time: 26ms

memory: 3540kb

input:

output:

result:

wrong answer Wrong Answer.

Subtask #4:

score: 10

Accepted

Dependency #2:

100%

Accepted

Test #7:

score: 10

Accepted

time: 245ms

memory: 3440kb

input:

output:

1
8
2
1 0 1 0 0 1 0 
5 3
7 1
5
1
0 1 0 1 
4 2
5
1
0 0 0 1 
3 1
3
1
1 1 1 1 1 
5 1
5
2
0 0 1 1 
3 2
3 0
8
2
0 1 1 1 1 0 0 
7 4
7 5
7
2
0 0 0 1 0 0 1 
6 1
6 0
5
2
0 0 0 1 
2 1
3 0
5
1
0 0 1 1 
4 3
6
2
1 0 1 0 0 
1 5
4 2
6
2
0 1 1 1 0 
1 2
4 0
5
1
0 0 0 0 1 
5 3
8
1
0 1 1 0 0 1 0 
7 1
6
1
0 1 1 1 0 
5 ...

result:

ok Accepted. Good Job!

Test #8:

score: 10

Accepted

time: 209ms

memory: 3456kb

input:

output:

1
5
2
1 0 1 0 0 
3 4
5 0
6
2
1 1 1 0 0 
4 3
5 2
6
2
0 1 0 0 1 
5 0
5 1
8
2
0 0 0 1 0 1 1 
7 1
7 2
8
4
1 1 1 0 0 0 0 0 0 1 
3 10
6 2
8 1
9 0
6
2
1 1 1 0 0 
5 1
5 3
8
2
1 0 0 1 1 1 1 
7 5
7 2
5
2
0 0 0 0 1 
3 0
5 1
6
1
1 1 0 1 0 
5 0
6
2
0 1 1 0 0 
5 0
5 3
6
2
0 0 1 0 1 
5 2
5 0
5
1
0 0 0 1 0 
5 4
6
2...

result:

ok Accepted. Good Job!

Subtask #5:

score: 0

Skipped

Dependency #3:

Subtask #6:

score: 10

Accepted

Dependency #4:

100%

Accepted

Test #11:

score: 10

Accepted

time: 1126ms

memory: 3504kb

input:

output:

1
7
2
1 0 1 0 0 1 1 
5 2
7 1
7
2
1 0 1 1 1 0 1 
5 4
6 2
7
2
1 1 0 1 1 0 0 
4 3
7 2
8
2
0 0 1 1 0 0 1 
4 6
5 0
8
2
0 1 0 0 0 0 1 
0 1
6 4
7
2
0 0 1 1 0 0 0 
4 1
6 2
5
1
0 1 1 0 
4 0
7
3
1 0 1 1 1 0 0 
2 0
3 1
7 4
4
2
0 1 0 
3 0
3 2
7
2
1 1 1 0 0 1 1 
5 4
6 3
7
2
0 1 1 0 1 1 
1 3
6 5
5
2
0 0 1 0 0 0 0...

result:

ok Accepted. Good Job!

Test #12:

score: 10

Accepted

time: 1439ms

memory: 3460kb

input:

output:

1
8
2
1 0 1 1 1 0 0 
7 3
7 0
7
2
1 0 0 1 1 0 1 
5 4
7 3
7
1
0 0 0 0 0 1 1 
7 6
7
3
1 1 0 1 0 1 1 
0 6
5 4
7 1
7
2
1 0 1 1 0 0 
3 2
5 1
7
2
1 0 1 0 0 1 1 
4 3
7 5
8
4
0 0 1 0 1 0 0 1 1 0 
6 1
7 5
9 0
10 4
8
2
0 1 0 0 1 0 0 
1 6
7 0
8
1
0 1 1 1 1 0 0 
7 6
7
3
0 0 0 0 1 0 1 
4 2
6 0
7 1
7
1
1 0 0 1 0 0...

result:

ok Accepted. Good Job!

Subtask #7:

score: 5

Accepted

Test #13:

score: 5

Accepted

time: 5ms

memory: 3460kb

input:

output:

1
3
1
0 0 0 0 0 0 0 0 0 0
5 10
8
1
0 0 0 0 0 0 0 0 0 0
4 10
8
1
0 0 0 0 0 0 0
5 0
4
1
0 0 0 0 0 0 0
7 4
8
1
0 0 0 0 0 0 0 0 0 0
8 10
7
1
0 0 0 0 0 0
1 3
5
1
0 0 0 0
4 0
7
1
0 0 0 0 0 0
4 2
11
1
0 0 0 0 0 0 0 0 0 0
5 7
4
1
0 0 0 0 0 0 0
4 7
8
1
0 0 0 0 0 0 0
5 6
4
1
0 0 0 0 0 0 0 0 0 0
3 4
8
1
0 0 0 ...

result:

ok Accepted. Good Job!

Subtask #8:

score: 0

Wrong Answer

Test #14:

score: 15

Accepted

time: 3183ms

memory: 3556kb

input:

output:

1
7
2
0 1 0 0 1 1 1 
6 2
7 0
8
2
0 0 0 1 1 0 0 
7 2
7 6
8
2
1 0 1 1 0 0 0 
4 1
6 2
8
2
0 1 0 0 1 0 1 
7 2
7 3
9
4
1 1 1 0 0 1 0 1 0 0 
4 3
5 2
6 0
8 1
6
2
0 0 1 1 1 0 1 
5 4
7 3
7
4
0 1 1 1 0 0 0 1 0 0 0 0 0 
10 6
11 3
12 8
13 0
6
1
0 1 1 0 0 
5 0
6
3
0 1 1 1 1 0 
3 2
4 1
6 0
10
2
1 1 0 0 1 0 0 0 0 ...

result:

ok Accepted. Good Job!

Test #15:

score: 0

Wrong Answer

time: 2963ms

memory: 3488kb

input:

output:

1
8
1
1 0 1 1 1 0 0 
7 0
8
2
1 1 0 0 0 1 1 
7 0
7 4
6
2
0 0 0 0 1 1 
3 2
4 0
6
2
0 0 0 1 0 
3 0
5 1
7
2
0 1 1 0 1 0 
3 0
5 1
7
3
0 0 0 0 1 0 1 
5 2
6 1
7 4
6
2
1 0 0 0 0 1 0 
6 5
7 4
8
2
1 1 1 0 1 0 1 
3 0
7 6
11
2
0 0 1 0 1 1 0 0 0 1 
10 9
10 5
8
2
1 1 1 0 1 0 0 
6 2
7 3
8
2
1 0 0 1 1 0 1 
4 2
6 7
...

result:

wrong answer Wrong Answer.

Subtask #9:

score: 10

Accepted

Dependency #6:

100%

Accepted

Dependency #7:

100%

Accepted

Test #17:

score: 10

Accepted

time: 2496ms

memory: 3552kb

input:

output:

1
7
2
0 1 1 1 0 0 1 
5 1
7 3
8
1
0 1 1 1 0 1 0 
7 3
10
4
0 0 1 1 1 1 0 1 0 1 0 0 0 1 1 0 
5 8
11 6
14 1
15 12
14
1
0 1 0 0 0 0 1 1 1 0 0 1 1 
13 9
7
2
0 0 1 0 0 1 0 
2 1
7 4
7
2
1 1 1 1 1 1 0 
6 0
7 3
8
2
1 1 1 0 1 1 0 
3 0
5 2
7
3
1 1 1 0 0 1 1 
5 0
6 2
7 1
8
4
1 0 1 0 0 1 0 0 0 1 
3 9
6 2
8 7
10 0...

result:

ok Accepted. Good Job!

Test #18:

score: 10

Accepted

time: 3541ms

memory: 3456kb

input:

output:

1
8
2
0 0 0 1 1 0 1 
7 1
7 6
8
4
1 1 0 0 0 0 1 0 0 1 
7 2
8 0
9 3
10 6
8
2
1 1 0 0 0 0 1 
4 1
7 6
7
2
1 1 0 1 0 0 
6 3
6 4
7
2
0 1 1 1 0 1 
6 2
6 5
8
4
0 0 1 0 0 1 0 1 0 1 
5 1
6 2
9 8
10 3
6
2
0 1 1 1 0 
0 4
5 2
7
2
1 0 0 0 0 0 1 
4 1
5 0
11
2
0 1 0 1 0 1 1 0 0 1 
10 5
10 0
7
3
1 0 0 0 1 0 0 
4 0
5...

result:

ok Accepted. Good Job!

Subtask #10:

score: 0

Skipped