oj.uz

Submission #748212

# Submission time Handle Problem Language Result Execution time Memory
748212 2023-05-25T16:09:06 Z Username4132 Friend (IOI14_friend) C++14
69 / 100
 1000 ms 49952 KB 
#include "friend.h"
#include<iostream>
#include<vector>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back

const int MAXN=100010;
int n, dp[2][MAXN], conf[MAXN], mt[MAXN], mini[11][11];
bool used[MAXN], even[MAXN];
vector<int> g[MAXN];
vector<int> base;

void dfs(int v, int p){
	dp[1][v]=conf[v];
	for(int to:g[v]) if(to!=p) {
		dfs(to, v);
		dp[1][v]+=dp[0][to];
		dp[0][v]+=dp[1][to];
	}
	dp[1][v]=max(dp[0][v], dp[1][v]);
}

int solve0(int confidence[], int host[]){
	forsn(i, 1, n) g[i].PB(host[i]), g[host[i]].PB(i);
	dfs(0, 0);
	return dp[1][0];
}

int solve1(int confidence[], int host[]){
	int sum=0;
	forn(i, n) sum+=confidence[i];
	return sum;
}

int solve2(int confidence[], int host[]){
	int mx=-1;
	forn(i, n) mx=max(mx, confidence[i]);
	return mx;
}

bool kuhn(int v){
	if(used[v]) return false;
	used[v]=true;
	for(int to:g[v]) if(mt[to]==-1 || kuhn(mt[to])){
		mt[to]=v;
		return true;
	}
	return false;
}

int solve3(int protocol[], int confidence[], int host[]){
	forsn(i, 1, n){
		if(protocol[i]==0){
			even[i]=!even[host[i]];
			g[host[i]].PB(i);
			g[i].PB(host[i]);
		}
		else{
			even[i]=even[host[i]];
			for(int to:g[host[i]]) g[i].PB(to), g[to].PB(i);
		}
	}
	forn(i, n) if(even[i]) base.PB(i);
	forn(i, n) mt[i]=-1;

	int ret=0;
	for(auto v:base){
		for(auto i:base) used[i]=false;
		ret+=kuhn(v);
	}
	return n-ret;
}

int solveTask(int task, int confidence[], int host[]){
	if(task==0) return solve0(confidence, host);
	else if(task==1) return solve1(confidence, host);
	else if(task==2) return solve2(confidence, host);
}

int miniSolve(int confidence[], int host[], int protocol[]){
	forsn(i, 1, n){
		if(protocol[i]==0) mini[i][host[i]]=mini[host[i]][i]=true;
		else{
			forn(j, n) if(mini[host[i]][j]) mini[i][j]=mini[j][i]=true;
			if(protocol[i]==2) mini[i][host[i]]=mini[host[i]][i]=true;
		}
	}

	int ret=-1;
	forn(mask, 1<<n){
		int sum=0;
		vector<int> cur;
		forn(i, n) if(mask&(1<<i)) cur.PB(i);
		bool wii=false;
		for(int u:cur) for(int v:cur) wii|=mini[u][v];
		if(wii) continue;
		for(int v:cur) sum+=confidence[v];
		ret=max(ret, sum);
	}
	return ret;
}

// Find out best sample
int findSample(int N, int confidence[], int host[], int protocol[]){
	n=N;

	if(n<=10) return miniSolve(confidence, host, protocol);


	forn(i, n) conf[i]=confidence[i];
	bool eq=true;
	forsn(i, 1, n-1) eq&=protocol[i]==protocol[i+1];
	if(eq) return solveTask(protocol[1], confidence, host);
	
	return solve3(protocol, confidence, host);

	return 0;
}

Compilation message

friend.cpp: In function 'int solveTask(int, int*, int*)':
friend.cpp:80:1: warning: control reaches end of non-void function [-Wreturn-type]
   80 | }
      | ^

Subtask #1
11.0 / 11.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

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

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 3 ms 2600 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2656 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 1 ms 2644 KB Output is correct
19 Correct 2 ms 2644 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2644 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Execution timed out 1071 ms 49952 KB Time limit exceeded
13 Halted 0 ms 0 KB -