Submission #4008843


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;

vector<P>loop(bool b){
	unordered_map<int,ll>mp;//連結成分ごとの最小値
	set<P>se;//コスト、連結成分
	vector<P>res;
	rep(i,n){
		int id=(b?n-i-1:i);
		if(se.empty()){
			res.push_back(P(INFL,-1));
		}
		else{
			auto it=se.begin();
			while(it!=se.end()&&it->second==uf.find(id))it++;
			if(it!=se.end()){
				res.push_back(P(d*i+it->first+a[i],it->second));
			}
			else{
				res.push_back(P(INFL,-1));
			}
		}
		ll cost=-i*d+a[i];
		if(!mp.count(uf.find(id))||cost<mp[uf.find(id)]){
			if(mp.count(uf.find(id)))se.erase(P(mp[uf.find(id)],uf.find(id)));
			mp[uf.find(id)]=cost;
			se.insert(P(cost,uf.find(id)));
		}
	}
	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]);
			swap(res2[i],res2[n-i-1]);
		}
		unordered_map<int,P>mp;
		rep(i,n){
			if(!mp.count(uf.find(i))||mp[uf.find(i)]>res[i]){
				mp[uf.find(i)]=res[i];
			}
			if(!mp.count(uf.find(i))||mp[uf.find(i)]>res2[i]){
				mp[uf.find(i)]=res2[i];
			}
		}
		for(auto p:mp){
			if(p.second.first==INFL)continue;
			if(!uf.same(p.first,p.second.second)){
				uf.unite(p.first,p.second.second);
				ans+=p.second.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 2227 Byte
Status
Exec Time 1133 ms
Memory 31328 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:79: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 483 ms 30688 KB
02.txt 464 ms 30688 KB
03.txt 467 ms 30944 KB
04.txt 450 ms 31072 KB
05.txt 436 ms 31200 KB
06.txt 378 ms 31200 KB
07.txt 330 ms 31200 KB
08.txt 414 ms 30432 KB
09.txt 366 ms 31328 KB
10.txt 422 ms 30944 KB
11.txt 1133 ms 30944 KB
12.txt 1111 ms 31328 KB
13.txt 1100 ms 30688 KB
14.txt 1130 ms 30432 KB
15.txt 1110 ms 30944 KB
16.txt 351 ms 30688 KB
17.txt 341 ms 30560 KB
18.txt 775 ms 31072 KB
19.txt 823 ms 30944 KB
20.txt 823 ms 30816 KB
21.txt 258 ms 30944 KB
22.txt 255 ms 30304 KB
23.txt 259 ms 30304 KB
24.txt 267 ms 31328 KB
25.txt 262 ms 31072 KB
26.txt 290 ms 30432 KB
27.txt 294 ms 30432 KB
28.txt 311 ms 30304 KB
29.txt 260 ms 30560 KB
30.txt 257 ms 30304 KB
s1.txt 1 ms 256 KB
s2.txt 1 ms 256 KB
s3.txt 2 ms 256 KB
s4.txt 1 ms 256 KB