QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#255501#5545. Contingency Plansentheta#WA 3ms8252kbC++202.2kb2023-11-18 16:08:032023-11-18 16:08:03

Judging History

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

  • [2023-11-18 16:08:03]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:8252kb
  • [2023-11-18 16:08:03]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define int long long
#define pii pair<int,int>
#define pb emplace_back
#define rep(i,a,b) for(int i=a; i < b; ++i)
#define owo ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define V vector

#define cerr if(1) cout
#define dbg(x) cerr << "?" << #x << " : " << x << endl;

void solve();
signed main(){
	owo
	int t = 1; //cin >> t
	while(t--) solve();
}

const int N = 1e5+5;


int n;
array<int,2> edg[N];
V<int> adj[N];

int r[4];

int d[N], p[N];
void dfs(int x,int par){
	for(int e : adj[x]){
		int y = edg[e][0]^edg[e][1]^x;
		if(y==par) continue;
		bool isr = 0;
		rep(i,0,4){
			isr |= y==r[i];
		}
		if(isr) continue;

		p[y] = p[x];
		d[y] = d[x]+1;
		dfs(y, x);
	}
}


bool g[4][4], gvis[4];
int gdfs(int x){
	if(gvis[x]) return 0;
	gvis[x] = 1;

	int ret = 1;
	rep(y,0,4) if(g[x][y]){
		ret += gdfs(y);
	}
	return ret;
}


void solve(){
	cin >> n;

	rep(e,1,n){
		int u, v;
		cin >> u >> v;

		edg[e] = {u,v};
		adj[u].push_back(e);
		adj[v].push_back(e);
	}

	r[1] = -1;
	rep(e,1,n){
		auto[u,v] = edg[e];
		if(adj[u].size()>=2 && adj[v].size()>=2){
			r[1] = u; r[2] = v; break;
		}
	}
	if(r[1]==-1){
		cout << -1 << '\n'; return;
	}

	for(int e : adj[r[1]]){
		int x = edg[e][0]^edg[e][1]^r[1];
		if(x!=r[2]){
			r[0] = x; break;
		}
	}
	for(int e : adj[r[2]]){
		int x = edg[e][0]^edg[e][1]^r[2];
		if(x!=r[1]){
			r[3] = x; break;
		}
	}

	rep(i,0,4){
		// dbg(r[i]);
		p[r[i]] = i;
		dfs(r[i], r[i]);
	}
	g[0][1] = g[1][2] = g[2][3] = 1;
	g[3][2] = g[2][1] = g[1][0] = 1;


	rep(e,1,n){
		auto[u,v] = edg[e];

		if(d[u]==0 && d[v]==0){
			int i = p[u], j = p[v];
			g[i][j] = g[j][i] = 0;

			bool found = 0;
			rep(ii,0,4) if(!found) rep(jj,0,ii-1) if(!found)
			if(!g[ii][jj]){
				g[ii][jj] = g[jj][ii] = 1;
				gvis[0] = gvis[1] = gvis[2] = gvis[3] = 0;
				if(gdfs(r[0])==4){
					found = 1;
					cout << r[ii] << " " << r[jj] << "\n";
				}
				else{
					g[ii][jj] = g[jj][ii] = 0;
				}
			}

		}
		else{
			if(!(d[u]<d[v])) swap(u,v);

			cout << v << " " << r[(p[v]+1)%4] << "\n";
		}

	}	


}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 7680kb

input:

7
1 2
3 7
2 4
2 5
1 3
3 6

output:

2 3
7 1
4 3
5 4
4 1
6 1

result:

ok AC

Test #2:

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

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

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

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

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

input:

5
2 1
2 3
2 4
4 5

output:

4 1
3 4
5 2
5 1

result:

ok AC

Test #5:

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

input:

5
1 4
3 4
4 5
2 5

output:

5 1
3 5
2 4
2 1

result:

ok AC

Test #6:

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

input:

5
5 2
1 2
4 2
3 4

output:

5 3
1 5
2 3
5 4

result:

ok AC

Test #7:

score: 0
Accepted
time: 3ms
memory: 7000kb

input:

20000
1 2
1 3
4 1
5 1
6 1
7 1
1 8
1 9
1 10
1 11
12 1
1 13
14 1
1 15
1 16
17 1
1 18
1 19
20 1
21 1
22 1
1 23
24 1
1 25
26 1
1 27
28 1
29 1
30 1
1 31
1 32
1 33
1 34
1 35
36 1
1 37
1 38
1 39
40 1
41 1
1 42
1 43
44 1
1 45
46 1
1 47
48 1
49 1
1 50
1 51
52 1
53 1
54 1
1 55
56 1
57 1
58 1
1 59
60 1
61 1
1 ...

output:

19999 2
3 19999
4 19999
5 19999
6 19999
7 19999
8 19999
9 19999
10 19999
11 19999
12 19999
13 19999
14 19999
15 19999
16 19999
17 19999
18 19999
19 19999
20 19999
21 19999
22 19999
23 19999
24 19999
25 19999
26 19999
27 19999
28 19999
29 19999
30 19999
31 19999
32 19999
33 19999
34 19999
35 19999
36...

result:

ok AC

Test #8:

score: -100
Wrong Answer
time: 3ms
memory: 8252kb

input:

20000
7662 1
9205 1
5971 1
1 9886
1 18853
14108 1
998 1
1 14958
7100 1
1 2670
1 18493
13838 1
4644 1
2139 1
1 18540
1 14081
1 16836
1 9357
245 1
242 1
1 13472
1 1471
3792 1
1 17875
13976 1
1 15085
1 17283
15014 1
17477 1
11578 1
18441 1
1 14367
3018 1
1 7186
1 4939
2470 1
2993 1
6175 1
1 19886
1 125...

output:

9205 7662
5971 7662
9886 7662
18853 7662
14108 7662
998 7662
14958 7662
7100 7662
2670 7662
18493 7662
13838 7662
4644 7662
2139 7662
18540 7662
14081 7662
16836 7662
9357 7662
245 7662
242 7662
13472 7662
1471 7662
3792 7662
17875 7662
13976 7662
15085 7662
17283 7662
15014 7662
17477 7662
11578 76...

result:

wrong output format Unexpected end of file - int32 expected