QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#136048#501. SubwayWawi0 0ms0kbC++202.4kb2023-08-06 19:58:172023-08-06 19:58:20

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-06 19:58:20]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-08-06 19:58:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<pair<int,int>> a;
vector<pair<int,int>> b;
vector<vector<int>> temp;
map<pair<int,int>,bool> mp;
int n; 
vector<bool> found;

int connected(int c){
    int curr=1;
    found[c]=true;
    for(auto cc:temp[c]){
        if(found[cc]) continue;
        curr+=connected(cc);
    }
    return curr;
}

void solve(){
    cin >> n;
    a.resize(n-1);
    temp.resize(n);
    for(int i=0; i < n-1;i++){
        cin >> a[i].first >> a[i].second;
        if(a[i].first > a[i].second) swap(a[i].first,a[i].second);
        temp[a[i].first].push_back(a[i].second);
        temp[a[i].second].push_back(a[i].first);
        mp[a[i]]=true;
    }
    int curr=0;
    for(int i=0; i < n-1;i++){
        int x,y; cin >> x >> y;
        if(mp[{x,y}]) continue;
        b.push_back({x,y}); 
        if(b[curr].first > b[curr].second) swap(b[curr].first,b[curr].second);
        mp[b[curr]]=true;
        curr++;
    }
    int size=0;
    vector<vector<int>> ans(curr);
    for(int i=0; i < curr;i++){
        found.clear();
        found.resize(n);
        for(int j=0; j < a.size();j++){
            temp[a[j].first].erase(find(temp[a[j].first].begin(),temp[a[j].first].end(),a[j].second));
            temp[a[j].second].erase(find(temp[a[j].second].begin(),temp[a[j].second].end(),a[j].first));
            temp[b[i].first].push_back(b[i].second);
            temp[b[i].second].push_back(b[i].first);
            if(connected(0)==n){
                ans[size].push_back(a[j].first);
                ans[size].push_back(a[j].second);
                ans[size].push_back(b[i].first);
                ans[size].push_back(b[i].second);
                a.erase(a.begin()+j);
                size++;
                break;
            } else{
                temp[b[i].first].erase(find(temp[b[i].first].begin(),temp[b[i].first].end(),b[i].second));
                temp[b[i].second].erase(find(temp[b[i].second].begin(),temp[b[i].second].end(),b[i].first));
                temp[a[j].first].push_back(a[j].second);
                temp[a[j].second].push_back(a[j].first);
            }
        }
    }
    cout << size << endl;
    for(auto c:ans) cout << c[1] << ' ' << c[0] << ' ' << c[3] << ' ' << c[2] << endl;
}

int32_t main() {
    ios::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    int t=1;
    // cin >> t;
    while(t--){
        solve();
    } 
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

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

output:

2
9 3 9 3
2 0 1 0

result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%