Submission #782121

#	Time	Username	Problem	Language	Result	Execution time	Memory
782121		I_Love_EliskaM_	Friend (IOI14_friend)	C++14	46 / 100	135 ms	65536 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;
const int inf=1e9;

struct DSU {
	vector<int> p,sz;
	DSU(int n) {
		forn(i,n) p.pb(i), sz.pb(1);
	}
	int get(int u) {
		return p[u]==u?u:get(p[u]);
	}
	void uni(int u, int v) {
		u=get(u), v=get(v);
		if (u==v) return;
		if (sz[u]<sz[v]) swap(u,v);
		p[v]=u;
		sz[u]+=sz[v];
	}
};

const int N=1e3+5;
int n;
bitset<N> adj[N];
bitset<N> was[N];
vector<int> g[N];
int a[N];
int dp[N][2];
int vis[N];

void dfs(int u, int p) {
	vis[u]=1;
	dp[u][1]=a[u];
	for(auto&v:g[u]) {
		if (v==p) continue;
		dfs(v,u);
		dp[u][0]+=max(dp[v][0],dp[v][1]);
		dp[u][1]+=dp[v][0];
	}
}

const int q = 998244353;
const int mod=1e9+7;

int findSample(int _n, int c[], int h[], int p[]) {
	n=_n;
	if (n>1000) return 0;
	forn(i,n) a[i]=c[i];
	if (n<=10) {
		for (int i=1; i<n; ++i) {
			if (p[i]) {
				forn(j,n) if (adj[h[i]][j]) adj[i][j]=adj[j][i]=1;
			}
			if (p[i]%2==0) {
				adj[h[i]][i]=adj[i][h[i]]=1;
			} 
		}
		int ans=0;
		forn(mask,1<<n) {
			vector<int> v;
			forn(i,n) if ((mask>>i)&1) v.pb(i);
			int f=0, s=0;
			for(auto&x:v) for(auto&y:v) f|=adj[x][y];
			for(auto&x:v) s+=a[x];
			if (!f) ans=max(ans,s);
		}
		return ans;
	}
	int z; 

	z=1;
	for (int i=1; i<n; ++i) z&=p[i]==1;
	if (z) {
		int s=0; forn(i,n) s+=a[i]; return s;
	}

	z=1;
	for (int i=1; i<n; ++i) z&=p[i]==2;
	if (z) {
		int s=0; forn(i,n) s=max(s,a[i]); return s;
	}

	z=1;
	for (int i=1; i<n; ++i) z&=p[i]==0;
	if (z) {
		for(int i=1; i<n; ++i) {
			g[h[i]].pb(i);
		}
		dfs(0,-1);
		return max(dp[0][0],dp[0][1]);
	}

	for (int i=1; i<n; ++i) {
		if (p[i]) {
			forn(j,n) if (adj[h[i]][j]) adj[i][j]=adj[j][i]=1;
		}
		if (p[i]%2==0) {
			adj[h[i]][i]=adj[i][h[i]]=1;
		} 
	}

	map<int,int> mp;
	DSU dsu(n);
	vector<int> hs(n);
	forn(i,n) {
		int p=1;
		forn(j,n) {
			if (adj[i][j]) {
				hs[i]=hs[i]+p;
				if (hs[i]>=mod) hs[i]-=mod;
			}
			p=(p*q)%mod;
		}
	}

	forn(i,n) {
		int s=hs[i];//hsh(i);
		if (mp.count(s)) {
			dsu.uni(i,mp[s]);
		} else mp[s]=i;
	}
	forn(i,n) forn(j,n) if (adj[i][j]) if (!was[dsu.get(i)][dsu.get(j)]) {
		g[dsu.get(i)].pb(dsu.get(j));
		was[dsu.get(i)][dsu.get(j)]=1;
	}
	forn(i,n) if (dsu.get(i)!=i) a[dsu.get(i)]+=a[i];

	int ans=0;
	forn(i,n) {
		if (vis[i]) continue;
		if (i!=dsu.get(i)) continue;
		dfs(i,-1);
		ans+=max(dp[i][0],dp[i][1]);
	}
	return ans;

}

• Subtask 1: 11 / 11
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31