Submission #328277

#	Time	Username	Problem	Language	Result	Execution time	Memory
328277		MrGary	timeismoney (balkan11_timeismoney)	C++11	75 / 100	2083 ms	18028 KiB

timeismoney

/*
{
######################
#       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;
	}
}
int cnt=0;
void solve(pair<LL,LL> l,pair<LL,LL> r){
	if(l==r) return;
	++cnt;
	if(cnt>=10000) return;
	LL k;
	k=(l.SEC-r.SEC);
	pair<pair<LL,LL>,vector<mp > > mid;
	mid=get(k,-(l.FIR-r.FIR));
	check(mid); 
	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 (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  111 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
timeismoney.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  114 |   scanf("%d%d%d%d",&a,&b,&c,&d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 75 / 100