Submission #4014901


Source Code Expand

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

class UnionFind {
	vector<int>par, sz;
public:
	UnionFind() {}
	UnionFind(int n) {
		par = sz = vector<int>(n);
		for (int i = 0; i < n; i++) {
			par[i] = i;
			sz[i] = 1;
		}
	}
	int find(int x) {
		if (par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y)return;
		if (sz[x] > sz[y]) {
			par[y] = x;
			sz[x] += sz[y];
		}
		else {
			par[x] = y;
			sz[y] += sz[x];
		}
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
	int size(int x) {
		return sz[find(x)];
	}
};

int n;ll d;
ll a[300000];
UnionFind uf;
ll mp[300000];

vector<P>loop(bool b){
	vector<P>res(n);
	rep(i,n)res[i]=P(INFL,-1),mp[i]=INFL;
	set<P>se;//コスト、連結成分
	rep(i,n){
		int id=(b?n-i-1:i);
		int p=uf.find(id);
		if(!se.empty()){
			auto it=se.begin();
			while(it!=se.end()&&it->second==p)it++;
			if(it!=se.end()){
				res[p]=min(res[p],P(d*i+it->first+a[i],it->second));
			}
		}
		ll cost=-i*d+a[i];
		if(cost<mp[p]){
			se.erase(P(mp[p],p));
			mp[p]=cost;
			se.insert(P(cost,p));
		}
		while(se.size()>2)se.erase(--se.end());
	}
	return res;
}
int main(){
	cin>>n>>d;
	rep(i,n)scanf("%lld",&a[i]);
	uf=UnionFind(n);
	ll ans=0;
	while(uf.size(0)!=n){
		auto res=loop(0);
		rep(i,n/2)swap(a[i],a[n-i-1]);
		auto res2=loop(1);
		rep(i,n/2)swap(a[i],a[n-i-1]);
		rep(i,n){
			res[i]=min(res[i],res2[i]);
			if(res[i].second==-1)continue;
			if(!uf.same(i,res[i].second)){
				uf.unite(i,res[i].second);
				ans+=res[i].first;
			}
		}
	}
	cout<<ans<<endl;
}

Submission Info

Submission Time
Task E - Connecting Cities
User autumn_eel
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1835 Byte
Status
Exec Time 350 ms
Memory 11840 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:76:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(i,n)scanf("%lld",&a[i]);
                             ^

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt, s4.txt
All 600 / 600 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, s1.txt, s2.txt, s3.txt, s4.txt
Case Name Status Exec Time Memory
01.txt 89 ms 11700 KB
02.txt 92 ms 11700 KB
03.txt 91 ms 11720 KB
04.txt 84 ms 11688 KB
05.txt 83 ms 11664 KB
06.txt 68 ms 11648 KB
07.txt 60 ms 11696 KB
08.txt 76 ms 11664 KB
09.txt 69 ms 11696 KB
10.txt 67 ms 11696 KB
11.txt 349 ms 11840 KB
12.txt 350 ms 11696 KB
13.txt 342 ms 11676 KB
14.txt 350 ms 11680 KB
15.txt 349 ms 11720 KB
16.txt 68 ms 11680 KB
17.txt 68 ms 11688 KB
18.txt 221 ms 11804 KB
19.txt 242 ms 11696 KB
20.txt 240 ms 11680 KB
21.txt 66 ms 11648 KB
22.txt 66 ms 11648 KB
23.txt 72 ms 11680 KB
24.txt 66 ms 11664 KB
25.txt 73 ms 11672 KB
26.txt 74 ms 11688 KB
27.txt 79 ms 11672 KB
28.txt 73 ms 11680 KB
29.txt 68 ms 11680 KB
30.txt 66 ms 11680 KB
s1.txt 2 ms 2304 KB
s2.txt 2 ms 2304 KB
s3.txt 2 ms 2304 KB
s4.txt 2 ms 2304 KB