Submission #4008779


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){
	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]);
		}
		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 0
Code Size 2207 Byte
Status
Exec Time 2104 ms
Memory 36624 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 0 / 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 1106 ms 34532 KB
02.txt 1080 ms 36332 KB
03.txt 1087 ms 34760 KB
04.txt 1036 ms 34464 KB
05.txt 990 ms 34492 KB
06.txt 1010 ms 35396 KB
07.txt 941 ms 34496 KB
08.txt 968 ms 34496 KB
09.txt 940 ms 34648 KB
10.txt 974 ms 34492 KB
11.txt 2104 ms 34660 KB
12.txt 2104 ms 36372 KB
13.txt 2104 ms 36548 KB
14.txt 2104 ms 34496 KB
15.txt 2104 ms 34776 KB
16.txt 951 ms 34576 KB
17.txt 957 ms 35872 KB
18.txt 1770 ms 35032 KB
19.txt 1737 ms 36240 KB
20.txt 1687 ms 34488 KB
21.txt 854 ms 36424 KB
22.txt 846 ms 34504 KB
23.txt 836 ms 36624 KB
24.txt 814 ms 34640 KB
25.txt 901 ms 35680 KB
26.txt 932 ms 35504 KB
27.txt 906 ms 35044 KB
28.txt 936 ms 34564 KB
29.txt 838 ms 34572 KB
30.txt 850 ms 34552 KB
s1.txt 1 ms 256 KB
s2.txt 1 ms 256 KB
s3.txt 1 ms 256 KB
s4.txt 1 ms 256 KB