답안 #328279

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
328279 2020-11-16T04:35:58 Z MrGary 시간이 돈 (balkan11_timeismoney) C++11
75 / 100
165 ms 1276 KB
/*
{
######################
#       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);
//	}
	assert(mid.FIR.FIR<=r.FIR&&mid.FIR.FIR>=l.FIR);
	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:114:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  114 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
timeismoney.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  117 |   scanf("%d%d%d%d",&a,&b,&c,&d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 384 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 384 KB Output is correct
8 Correct 6 ms 748 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 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 7 ms 364 KB Output is correct
15 Correct 5 ms 364 KB Output is correct
16 Runtime error 29 ms 620 KB Execution killed with signal 6 (could be triggered by violating memory limits)
17 Runtime error 30 ms 620 KB Execution killed with signal 6 (could be triggered by violating memory limits)
18 Runtime error 76 ms 748 KB Execution killed with signal 6 (could be triggered by violating memory limits)
19 Runtime error 165 ms 1276 KB Execution killed with signal 6 (could be triggered by violating memory limits)
20 Runtime error 94 ms 1000 KB Execution killed with signal 6 (could be triggered by violating memory limits)