oj.uz

답안 #782037

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
782037 2023-07-13T14:57:52 Z I_Love_EliskaM_ 친구 (IOI14_friend) C++14
46 / 100
 25 ms 1484 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;


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

int dfs(int u) {
	int r=a[u];
	vis[u]=1;
	forn(i,N) if (adj[u][i]) {
		if (vis[i]) continue;
		c[i]=c[u]^1;
		r+=dfs(i);
	}	
	return r;
}
int sum(int u) {
	int r=c[u]*a[u];
	vis[u]=2;
	forn(i,N) if (adj[u][i]) {
		if (vis[i]==2) continue;
		r+=sum(i);
	}	
	return r;
}

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

int findSample(int n, int c[], int h[], int p[]) {
	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]);
	}

	int ans=0;
	forn(i,n) {
		if (vis[i]) continue;
		int sz=dfs(i);
		int x=sum(i);
		ans+=max(sz-x,x);
	}
	return ans;

}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Incorrect 1 ms 340 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Incorrect 25 ms 1484 KB Output isn't correct
13 Halted 0 ms 0 KB -