Submission #108077

#	Time	Username	Problem	Language	Result	Execution time	Memory
108077		autumn_eel	Palembang Bridges (APIO15_bridge)	C++14	31 / 100	2053 ms	2560 KiB

bridge

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

map<int,int>bit[2];
void add(int t,int k,int x){
	while(k<=1e9){
		bit[t][k]+=x;
		k+=k&-k;
	}
}
int sum(int t,int k){
	int res=0;
	while(k){
		res+=bit[t][k];
		k-=k&-k;
	}
	return res;
}

char p[200000][2],q[200000][2];
int s[200000],t[200000];
int main(){
	int K,n;cin>>K>>n;
	if(K==1){
		vector<int>v;
		ll sum=0;
		rep(i,n){
			scanf("%s%d%s%d",p[i],&s[i],q[i],&t[i]);
			if(p[i][0]==q[i][0]){
				sum+=abs(s[i]-t[i]);
				continue;
			}
			sum++;
			v.push_back(s[i]);
			v.push_back(t[i]);
		}
		sort(v.begin(),v.end());
		int md=v[v.size()/2];
		for(int i:v)sum+=abs(i-md);
		cout<<sum<<endl;
		return 0;
	}
	ll sum=0;
	vector<P>v;
	vector<int>xs;
	rep(i,n){
		scanf("%s%d%s%d",p[i],&s[i],q[i],&t[i]);
		if(p[i][0]==q[i][0]){
			sum+=abs(s[i]-t[i]);
			continue;
		}
		sum++;
		v.push_back(P(min(s[i],t[i]),max(s[i],t[i])));
		xs.push_back(s[i]);
		xs.push_back(t[i]);
	}
	ll Min=LLONG_MAX;
	rep(i,xs.size())rep(j,xs.size()){
		ll cnt=0;
		rep(k,v.size()){
			cnt+=min(abs(xs[i]-v[k].first)+abs(xs[i]-v[k].second),
					abs(xs[j]-v[k].first)+abs(xs[j]-v[k].second));
		}
		Min=min(Min,cnt);
	}
	cout<<sum+(v.empty()?0:Min)<<endl;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:2:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n)for(int i=0;i<(n);i++)
                              ^
bridge.cpp:61:2: note: in expansion of macro 'rep'
  rep(i,xs.size())rep(j,xs.size()){
  ^~~
bridge.cpp:2:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n)for(int i=0;i<(n);i++)
                              ^
bridge.cpp:61:18: note: in expansion of macro 'rep'
  rep(i,xs.size())rep(j,xs.size()){
                  ^~~
bridge.cpp:2:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n)for(int i=0;i<(n);i++)
                              ^
bridge.cpp:63:3: note: in expansion of macro 'rep'
   rep(k,v.size()){
   ^~~
bridge.cpp:31:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s%d%s%d",p[i],&s[i],q[i],&t[i]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d%s%d",p[i],&s[i],q[i],&t[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37