/*
{
######################
# Author #
# Gary #
# 2020 #
######################
*/
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
// int x=0;
// char ch=getchar();
// while(ch<'0'||ch>'9'){
// ch=getchar();
// }
// while(ch>='0'&&ch<='9'){
// x=(x<<1)+(x<<3)+(ch^48);
// ch=getchar();
// }
// return x;
//}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
LL x,y;
vector<pair<mp,mp> > e;
bool cmp(pair<mp,mp> A,pair<mp,mp> B){
return x*A.SEC.FIR+y*A.SEC.SEC<x*B.SEC.FIR+y*B.SEC.SEC;
}
const int MAXN=202;
int n,m;
#define x1 O000OO0oO00ooO
#define x2 O000OO000oo0Oo0oo
#define y1 OO000OO0oO00ooO
#define y2 oO000OO000oo0Oo0oo
int fa[MAXN];
int root(int x){
return fa[x]=(fa[x]==x? x:root(fa[x]));
}
pair<pair<LL,LL> ,vector<mp> > MST(){
sort(ALL(e),cmp);
LL sumx,sumy;
sumx=sumy=0;
rb(i,1,n) fa[i]=i;
vector<mp> edges;
for(auto it:e){
int u,v;
int X,Y;
X=it.SEC.FIR;
Y=it.SEC.SEC;
u=it.FIR.FIR;
v=it.FIR.SEC;
if(root(u)!=root(v)){
fa[root(u)]=root(v);
edges.PB(II(u,v));
sumx+=X;
sumy+=Y;
}
}
return II(II(sumx,sumy),edges);
}
pair<pair<LL,LL> ,vector<mp> > get(LL X,LL Y){
x=X,y=Y;
return MST();
}
pair<pair<LL,LL> ,vector<mp> > rest;
void check(pair<pair<LL,LL> ,vector<mp > > E){
if(E.FIR.FIR*E.FIR.SEC<rest.FIR.FIR*rest.FIR.SEC){
rest=E;
}
}
void solve(pair<LL,LL> l,pair<LL,LL> r){
if(l.FIR==r.FIR) return;
LL k;
k=(r.SEC-l.SEC);
pair<pair<LL,LL>,vector<mp > > mid;
mid=get(-k,(r.FIR-l.FIR));
check(mid);
// printf("(%d %d),(%d %d),(%d %d)\n",l.FIR,l.SEC,mid.FIR.FIR,mid.FIR.SEC,r.FIR,r.SEC);
// if(!(mid.FIR.FIR<=r.FIR&&mid.FIR.FIR>=l.FIR)){
// cout<<"!";
// exit(0);
// }
if(mid.FIR.FIR<=r.FIR&&mid.FIR.FIR>=l.FIR);
else return;
if(mid.FIR==l||mid.FIR==r) return;
solve(l,mid.FIR);
solve(mid.FIR,r);
}
int main(){
scanf("%d%d",&n,&m);
rb(i,1,m){
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
a++;
b++;
e.PB(II(II(a,b),II(c,d)));
}
pair<pair<LL,LL> ,vector<mp> > lll,rrr;
rest.FIR.FIR=rest.FIR.SEC=1e9;
lll=get(1,0);
rrr=get(0,1);
check(lll);
check(rrr);
solve(lll.FIR,rrr.FIR);
printf("%lld %lld\n",rest.FIR.FIR,rest.FIR.SEC);
for(auto it:rest.SEC){
printf("%d %d\n",it.FIR-1,it.SEC-1);
}
return 0;
}
/** 程序框架：
*
*
*
*
**/
Compilation message
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:115:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
115 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
timeismoney.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
118 | scanf("%d%d%d%d",&a,&b,&c,&d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
0 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
2 ms |
364 KB |
Output is correct |
| 8 |
Correct |
6 ms |
748 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
0 ms |
364 KB |
Output is correct |
| 11 |
Correct |
0 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
8 ms |
364 KB |
Output is correct |
| 15 |
Correct |
5 ms |
364 KB |
Output is correct |
| 16 |
Correct |
106 ms |
364 KB |
Output is correct |
| 17 |
Correct |
112 ms |
364 KB |
Output is correct |
| 18 |
Correct |
105 ms |
492 KB |
Output is correct |
| 19 |
Correct |
909 ms |
748 KB |
Output is correct |
| 20 |
Correct |
931 ms |
768 KB |
Output is correct |
