Submission #4014894


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]){
			if(mp[p]!=INFL)se.erase(P(mp[p],p));
			mp[p]=cost;
			se.insert(P(cost,p));
		}
	}
	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 1807 Byte
Status
Exec Time 721 ms
Memory 24192 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:75: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 272 ms 24192 KB
02.txt 261 ms 24192 KB
03.txt 265 ms 24064 KB
04.txt 257 ms 24064 KB
05.txt 271 ms 24064 KB
06.txt 235 ms 24064 KB
07.txt 233 ms 24064 KB
08.txt 255 ms 24064 KB
09.txt 248 ms 24192 KB
10.txt 241 ms 24064 KB
11.txt 713 ms 24192 KB
12.txt 701 ms 24064 KB
13.txt 677 ms 24064 KB
14.txt 705 ms 24064 KB
15.txt 721 ms 24192 KB
16.txt 236 ms 24064 KB
17.txt 223 ms 24064 KB
18.txt 405 ms 24192 KB
19.txt 423 ms 24064 KB
20.txt 411 ms 24064 KB
21.txt 166 ms 24064 KB
22.txt 158 ms 24064 KB
23.txt 162 ms 24064 KB
24.txt 178 ms 24192 KB
25.txt 165 ms 24192 KB
26.txt 191 ms 24064 KB
27.txt 210 ms 24192 KB
28.txt 213 ms 24064 KB
29.txt 162 ms 24064 KB
30.txt 155 ms 24192 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