QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#652741 | #4569. Connect the Points | IllusionaryDominance# | AC ✓ | 1ms | 3880kb | C++14 | 1.8kb | 2024-10-18 19:04:34 | 2024-10-18 19:04:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
vector<pair<int,int>> a(3);
for(int i=0;i<3;++i) cin>>a[i].first>>a[i].second;
for(int i=0;i<3;++i) for(int j=0;j<3;++j) if(i!=j) a.push_back({a[i].first, a[j].second});
int ALL=6;
pair<long long, vector<tuple<int,int,int,int>>> ans={-1, vector<tuple<int,int,int,int>>()};
for(int j=0;j<(1<<ALL);++j)
{
vector<pair<int,int>> b;
b.push_back(a[0]); b.push_back(a[1]); b.push_back(a[2]);
vector<tuple<int,int,int>> ed;
for(int i=0;i<ALL;++i) if(j>>i&1) b.push_back(a[i+3]);
for(int i=0;i<b.size();++i) for(int jj=i+1;jj<b.size();++jj)
{
if(b[i].first==b[jj].first) ed.push_back({abs(b[i].second - b[jj].second), i, jj});
else if(b[i].second==b[jj].second)
ed.push_back({abs(b[i].first-b[jj].first), i, jj});
}
sort(ed.begin(), ed.end());
vector<int> fa(b.size());
for(int i=0;i<b.size();++i) fa[i]=i;
function<int(int)> getf = [&](int x) { return fa[x]==x?x:fa[x]=getf(fa[x]); };
vector<tuple<int,int,int,int>> v;
int _=0;
for(int i=0;i<ed.size();++i)
{
auto [w, x, y] = ed[i];
// x=getf(x), y=getf(y);
if(getf(x)!=getf(y))
{
fa[getf(x)]=getf(y), _+=w;
if(b[x]!=b[y]) v.push_back({b[x].first, b[x].second, b[y].first, b[y].second});
}
}
if(getf(0)==getf(1)&&getf(1)==getf(2))
if(ans.first==-1||ans.first>_) ans={_, v};
}
cout << ans.second.size() << "\n";
for(auto [x, y, xx, yy] : ans.second) cout<<x<<" "<<y<<" "<<xx<<" "<<yy<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3880kb
input:
1 1 3 5 8 6
output:
4 3 5 3 6 3 5 1 5 1 1 1 5 8 6 3 6
result:
ok Total length is 12
Test #2:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
1 1 2 2 3 3
output:
4 1 1 1 2 2 2 1 2 2 2 2 3 3 3 2 3
result:
ok Total length is 4
Test #3:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
1 1 2 3 3 2
output:
4 1 1 1 2 2 3 2 2 3 2 2 2 1 2 2 2
result:
ok Total length is 4
Test #4:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
1 2 2 1 3 3
output:
4 1 2 2 2 2 1 2 2 3 3 2 3 2 2 2 3
result:
ok Total length is 4
Test #5:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
1 2 2 3 3 1
output:
4 1 2 2 2 2 3 2 2 3 1 2 1 2 2 2 1
result:
ok Total length is 4
Test #6:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
1 3 2 1 3 2
output:
4 1 3 1 2 2 1 2 2 3 2 2 2 1 2 2 2
result:
ok Total length is 4
Test #7:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
1 3 2 2 3 1
output:
4 1 3 1 2 2 2 1 2 2 2 2 1 3 1 2 1
result:
ok Total length is 4
Test #8:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
-811089219 -147580223 -131318959 -47863115 180743101 601547107
output:
4 -811089219 -147580223 -811089219 -47863115 180743101 601547107 -131318959 601547107 -131318959 -47863115 -131318959 601547107 -131318959 -47863115 -811089219 -47863115
result:
ok Total length is 1740959650
Test #9:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
-953648657 -254962225 -198962039 539064186 536177467 -81912224
output:
4 -953648657 -254962225 -953648657 -81912224 -198962039 539064186 -198962039 -81912224 536177467 -81912224 -198962039 -81912224 -953648657 -81912224 -198962039 -81912224
result:
ok Total length is 2283852535
Test #10:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
170075350 644693857 -70945648 -531201615 -813420873 75995752
output:
4 170075350 75995752 -70945648 75995752 170075350 644693857 170075350 75995752 -70945648 -531201615 -70945648 75995752 -813420873 75995752 -70945648 75995752
result:
ok Total length is 2159391695
Test #11:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
-598308052 155442794 -752953801 111986435 782202531 -333732768
output:
4 -598308052 155442794 -598308052 111986435 -752953801 111986435 -598308052 111986435 -598308052 111986435 -598308052 -333732768 782202531 -333732768 -598308052 -333732768
result:
ok Total length is 2024331894
Test #12:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
140537651 392873314 856272625 199854620 284394957 -862945504
output:
4 140537651 199854620 284394957 199854620 140537651 392873314 140537651 199854620 856272625 199854620 284394957 199854620 284394957 -862945504 284394957 199854620
result:
ok Total length is 1971553792
Test #13:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
-531600195 66788696 495972018 -828643104 -537934741 235845303
output:
4 -537934741 235845303 -531600195 235845303 -531600195 66788696 -531600195 235845303 -531600195 66788696 -531600195 -828643104 495972018 -828643104 -531600195 -828643104
result:
ok Total length is 2098395166
Test #14:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
-565864098 -762723255 903590907 -762723255 -486054726 -762723255
output:
2 -565864098 -762723255 -486054726 -762723255 903590907 -762723255 -486054726 -762723255
result:
ok Total length is 1469455005
Test #15:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
80565983 -977814210 80565983 384343197 80565983 102575609
output:
2 80565983 384343197 80565983 102575609 80565983 -977814210 80565983 102575609
result:
ok Total length is 1362157407
Test #16:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
435839201 -838682337 435839201 821052661 499609215 273341058
output:
3 499609215 273341058 435839201 273341058 435839201 821052661 435839201 273341058 435839201 -838682337 435839201 273341058
result:
ok Total length is 1723505012
Test #17:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
435839201 273341058 499609215 821052661 435839201 -838682337
output:
3 499609215 821052661 435839201 821052661 435839201 273341058 435839201 821052661 435839201 273341058 435839201 -838682337
result:
ok Total length is 1723505012
Test #18:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
-550183491 -223052429 756776472 349902936 239047012 -223052429
output:
3 239047012 -223052429 756776472 -223052429 756776472 349902936 756776472 -223052429 -550183491 -223052429 239047012 -223052429
result:
ok Total length is 1879915328
Test #19:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
1000000000 894586329 -444648850 -239939045 -733796075 -301669878
output:
4 -444648850 -239939045 -444648850 -301669878 -733796075 -301669878 -444648850 -301669878 1000000000 894586329 1000000000 -239939045 -444648850 -239939045 1000000000 -239939045
result:
ok Total length is 2930052282
Test #20:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
669699982 91018932 438054159 1000000000 -364758687 -418769264
output:
4 669699982 91018932 438054159 91018932 438054159 91018932 438054159 -418769264 -364758687 -418769264 438054159 -418769264 438054159 1000000000 438054159 91018932
result:
ok Total length is 2453227933
Test #21:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
-1000000000 -167957680 247368494 215997643 -384275539 -796580213
output:
4 247368494 215997643 247368494 -167957680 -1000000000 -167957680 -384275539 -167957680 -384275539 -796580213 -384275539 -167957680 247368494 -167957680 -384275539 -167957680
result:
ok Total length is 2259946350
Test #22:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
-619431287 -131966997 616405883 224993162 793394764 -1000000000
output:
4 793394764 -1000000000 616405883 -1000000000 616405883 224993162 616405883 -131966997 616405883 -131966997 616405883 -1000000000 -619431287 -131966997 616405883 -131966997
result:
ok Total length is 2637819213
Test #23:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
1000000000 127343545 -28934934 951599244 274060166 -1000000000
output:
4 -28934934 127343545 274060166 127343545 1000000000 127343545 274060166 127343545 -28934934 951599244 -28934934 127343545 274060166 -1000000000 274060166 127343545
result:
ok Total length is 2980534178
Test #24:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
-950000000 950000000 629494532 268139913 853768075 -8108129
output:
4 853768075 -8108129 629494532 -8108129 629494532 268139913 629494532 -8108129 -950000000 950000000 -950000000 268139913 629494532 268139913 -950000000 268139913
result:
ok Total length is 2761876204