QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#135693 | #501. Subway | Wawi | 0 | 0ms | 0kb | C++20 | 2.5kb | 2023-08-05 22:12:40 | 2023-08-05 22:12:42 |
Judging History
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);
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[0] << ' ' << c[1] << ' ' << c[2] << ' ' << c[3] << endl;
}
int32_t main() {
ios::sync_with_stdio(false);cout.tie(0);cin.tie(0);
int t=1;
// cin >> t;
while(t--){
solve();
}
}
詳細信息
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 3 9 3 9 0 2 0 1
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%