oj.uz

Submission #782143

# Submission time Handle Problem Language Result Execution time Memory
782143 2023-07-13T15:37:34 Z I_Love_EliskaM_ Friend (IOI14_friend) C++14
46 / 100
 20 ms 1392 KB 
#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> 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];
	forn(v,n) {
		if (!g[u][v]) continue;
		if (v==p) continue;
		if (vis[v]) 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]][i]=1;
		}
		dfs(0,0);
		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];
		if (mp.count(s)) {
			dsu.uni(i,mp[s]);
		} else mp[s]=i;
	}
	forn(i,n) forn(j,n) if (adj[i][j]) g[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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Incorrect 2 ms 468 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 240 KB Output is correct
12 Incorrect 20 ms 1392 KB Output isn't correct
13 Halted 0 ms 0 KB -