提出 #494537

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)c.size())
#define ten(c) ((int)1e##c)

class UF{
	int n;
	vector<int> d;
	public:
	UF(int n) : n(n) , d(n, -1){}
	bool same(int a,int b) { return find(a) == find(b); }
	int find(int a) { return d[a] < 0 ? a :  (d[a] = find(d[a])) ; }
	bool unite(int a,int b ){
		a = find(a),b = find(b);
		if(a==b)return false;
		if(d[a] > d[b]) swap(a,b);
		d[a] += d[b];
		d[b] = a;
		n--;
		return true;
	}
	int size() { return n; }
	
};

typedef pair<int,int > Pii;

int c[ten(5)];
vector<int> e[ten(5)];
int ans[ten(5)],maxes[ten(5)];

int main(){
	int n,m;
	vector<Pii> edges;
	while(cin>>n){
		memset(c,0,sizeof(c));
		FOR(i,n) e[i].clear();
		memset(ans,0,sizeof(ans));
		memset(maxes,0,sizeof(maxes));
		FOR(i,n) cin>>c[i];
		cin>>m;
		FOR(i,m) {
			int a,b; cin>>a>>b;
			a--; b--;
			edges.emplace_back(a,b);
			e[a].push_back(b);
			e[b].push_back(a);
		}
			
		UF uf(n);
		for(auto kv : edges) if(c[kv.first] == c[kv.second]) uf.unite(kv.first,kv.second);
		FOR(i,n) {
			sort(e[i].begin(),e[i].end(),[](const int& a,const int &b){
				return c[a] < c[b];
			});
			FOR(j,sz(e[i])-1){
				int x = e[i][j],y = e[i][j+1];
				if(c[x] == c[y]) {
					uf.unite(x,y);
				}
			}
		}
		
		map<int,vector<int>> mp;
		FOR(i,n) mp[uf.find(i)].push_back(i);
		vector<int> ids;
		for(auto x : mp) ids.push_back(x.first);
		sort(ids.begin(),ids.end(),[](const int&a,const int& b){
			return c[a] < c[b];
		});

		for(auto u : ids) {
			auto& grp = mp[u];
			int mx = 0;
			for(auto x : grp) {
				mx = max(mx,maxes[x]);
				for(auto to : e[x]) mx = max(mx,maxes[to]);
			}
			
			//set anses
			for(auto x : grp) ans[x] = mx + 1;
			
			//set maxes
			for(auto x : grp) {
				maxes[x] = ans[x];
				for(auto to : e[x]) maxes[to] = ans[x];
			}
		}
		
		ll out = 0;
		FOR(i,n) out += ans[i];
		
		cout << out << endl;
	}
	return 0;
}

提出情報

ジャッジ結果