QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#258233#5545. Contingency Planhank55663#TL 2ms6252kbC++142.0kb2023-11-19 16:11:502023-11-19 16:11:51

Judging History

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

  • [2023-11-19 16:11:51]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:6252kb
  • [2023-11-19 16:11:50]
  • 提交

answer

#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define pdd pair<double,double>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define mp make_pair
#define LL long long
#define ULL unsigned long long
#define sqr(x) ((x)*(x))
#define pi acos(-1)
#define MEM(x) memset(x,0,sizeof(x))
#define MEMS(x) memset(x,-1,sizeof(x))
using namespace std;
vector<pii> v[100005];
int val[100005];
void dfs(int x,int f){
    for(auto it:v[x]){
        if(it.x!=f){
            dfs(it.x,x);
            val[it.y]=it.x;
        }
    }
}
void solve(int T){
    int n;
    scanf("%d",&n);
    set<pii> s;
    for(int i = 1;i<n;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        v[x].pb(mp(y,i));
        v[y].pb(mp(x,i));
        s.insert(mp(x,y));
        s.insert(mp(y,x));
    }
    for(int i = 1;i<=n;i++){
        if(v[i].size()==n-1){
            printf("-1\n");
            return;
        }
    }
    for(int i = 1;i<=n;i++){
        if(v[i].size()==1&&v[i][0].y!=1){
            dfs(i,0);
            vector<pii> ans;
            for(int j = 1;j<n;j++){
                if(val[j]!=v[i][0].x){
                    //printf("%d %d\n",i,val[j]);
                    ans.pb(mp(i,val[j]));
                }
                else{
                    for(int k=1;k<j;k++){
                        if(s.find(mp(val[k],val[j]))==s.end()){
                            ans.pb(mp(val[k],val[j]));
                            break;
                        }
                    }
                    //printf("%d %d\n",val[1],val[j]);
                }
                
            }
            if(ans.size()==n-1){
                for(auto it:ans){
                    printf("%d %d\n",it.x,it.y);
                }
                return ;
            }
        }
    }
} 

int main(){
    int t=1;
     //scanf("%d",&t);
    for(int i = 1;i<=t;i++){
     //   cerr<<i<<endl;
        solve(i);
    }
}
/*
1227076727
1919786269
1261786217
1924134973
1051246577

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok AC

Test #2:

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

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

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

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

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

input:

5
2 1
2 3
2 4
4 5

output:

5 1
5 3
5 2
1 4

result:

ok AC

Test #5:

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

input:

5
1 4
3 4
4 5
2 5

output:

2 1
2 3
2 4
1 5

result:

ok AC

Test #6:

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

input:

5
5 2
1 2
4 2
3 4

output:

3 5
3 1
3 2
5 4

result:

ok AC

Test #7:

score: -100
Time Limit Exceeded

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:


result: