oj.uz

Submission #105359

# Submission time Handle Problem Language Result Execution time Memory
105359 2019-04-11T14:11:52 Z TuGSGeReL Friend (IOI14_friend) C++14
46 / 100
 973 ms 11000 KB 
        #include "friend.h"
        #include <bits/stdc++.h>
        #include <ext/pb_ds/assoc_container.hpp>
         
        using namespace std;
        using namespace __gnu_pbds;
         
        #define ll long long
        #define mp make_pair
        #define pub push_back
        #define pob pop_back()
        #define ss second
        #define ff first
        #define mt make_tuple
        #define pof pop_front()
        #define fbo find_by_order
        #define ook order_of_key
         
        typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
        using pll = pair <ll, ll>;
        using pii = pair <int, int>;
         
        int used[2001], pre[3], dp[2001][2], idx, par[2001], fl[2001][2001];
        vector <int> edg[2001];
        pair<int, int> p[1001];
         
        int solve1(int n, int confidence[], int host[], int protocol[])
        {
        	
        	int ans = 0;
        	
        	for (int i = 1; i < n; i++)
        	{
        		if ( !protocol[i] )
        		{
        			edg[i].pub(host[i]);
        			edg[host[i]].pub(i);
        		} else if ( protocol[i] == 1 )
        		{
        			for (int j = 0; j < edg[host[i]].size(); j++)
        			{
        				edg[edg[host[i]][j]].pub(i);
        				edg[i].pub(edg[host[i]][j]);
        			}
        		} else {
        			for (int j = 0; j < edg[host[i]].size(); j++)
        			{
        				edg[i].pub(edg[host[i]][j]);
        				edg[edg[host[i]][j]].pub(i);
        			}
         
        			edg[i].pub(host[i]);
        			edg[host[i]].pub(i);
        		}
        	}
        	
        	for (int i = 0; i < (1 << n); i++)
        	{
        		memset(used, 0, sizeof used);
        		bool boo = 0;
        		int res = 0;
         
        		for (int j = 0; j < n; j++)
        		{
        			if ( i & (1 << j) )
        			{
        				for ( auto x : edg[j] )
        					if ( used[x] )
        						boo = 1;
         
        				res += confidence[j];
        				used[j] = 1;
        			}
        		}
         
        		if ( !boo )
        			ans = max(ans, res);
        	}
        	
        	return ans;
        }
         
        void dfs(int u, int par)
        {
        	bool boo = 1;
        	for (auto x : edg[u])
        		if ( x != par )
        			dfs(x, u), boo = 0;
        	
        	if ( par != -1 )
        	{
        		dp[par][0] += max(dp[u][1], dp[u][0]);
        		dp[par][1] += dp[u][0];
        	}
        }
         
        bool bfs(int u)
        {
        	memset(used, 0, sizeof used);
        	used[u] = 1;
        	par[u] = -1;
        	queue<int>q;
        	q.push(u);
        	
        	while (!q.empty())
        	{
        		u = q.front();
        		q.pop();
        		
        		for (int i = 0; i <= idx + 1; i++)
        		{
        			if ( fl[u][i] && !used[i] )
        			{
        				used[i] = 1;
        				par[i] = u;
        				q.push(i);
        			}
        		}
        	}
        	
        	if ( used[idx + 1] )
        		return 1;
        	
        	return 0;
        }
         
        int findSample(int n,int confidence[],int host[],int protocol[]){
        	
        	if ( n <= 10 )
        		return solve1(n, confidence, host, protocol);
        	
        	for (int i = 1; i < n; i++)
        		pre[protocol[i]]++;
        	
        	if ( pre[1] == n - 1 )
        	{
        		int ans = 0;
        		
        		for (int i = 0; i < n; i++)
        			ans += confidence[i];
        		
        		return ans;
        	}
        	
        	if ( pre[2] == n - 1 )
        	{
        		int ans = 0;
        		
        		for (int i = 0; i < n; i++)
        			ans = max(ans, confidence[i]);
        		
        		return ans;
        	}
        	
        	if ( pre[0] == n - 1 )
        	{
        		for (int i = 1; i < n; i++)
        		{
        			edg[host[i]].pub(i);
        			edg[i].pub(host[i]);
        		}
        		
        		for (int i = 0; i < n; i++)
        			dp[i][1] = confidence[i];
        		
        		dfs(0, -1);
        		
        		return max(dp[0][0], dp[0][1]);
        	}
         
        	for (int i = 0; i < n - 1; i++)
        	{
        		p[i].ff = ++idx;
              fl[0][idx] = 1;
        		p[i].ss = ++idx;
        		fl[p[i].ff][p[i].ss] = 1;
        	}
        	
        	p[n - 1].ff = ++idx;
        	
        	for (int i = 1; i < n; i++)
        	{
        		if ( !protocol[i] )
        		{
        			edg[i].pub(host[i]);
        			edg[host[i]].pub(i);
        			fl[p[host[i]].ss][p[i].ff] = 1;
        		} else {
        			for (auto x : edg[host[i]])
        			{
        				fl[p[x].ss][p[i].ff] = 1;
        				edg[x].pub(i);
        	        	edg[i].pub(x);
        			}
        		}
        	}
        	for (int i = 0; i <= idx; i++)
              	fl[p[i].ss][idx + 1] = 1;
        	int ans = 0;
        	
        	while (bfs(0))
        	{
        		for (int i = idx + 1; par[i] != -1; i = par[i])
        			fl[par[i]][i]--, fl[i][par[i]]++;
        		ans++;
        	}
        	
        	return ans;
        }

Compilation message

friend.cpp: In function 'int solve1(int, int*, int*, int*)':
friend.cpp:40:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
            for (int j = 0; j < edg[host[i]].size(); j++)
                            ~~^~~~~~~~~~~~~~~~~~~~~
friend.cpp:46:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
            for (int j = 0; j < edg[host[i]].size(); j++)
                            ~~^~~~~~~~~~~~~~~~~~~~~
friend.cpp: In function 'void dfs(int, int)':
friend.cpp:85:15: warning: variable 'boo' set but not used [-Wunused-but-set-variable]
          bool boo = 1;
               ^~~

Subtask #1
11.0 / 11.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 480 KB Output is correct
3 Correct 3 ms 356 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 1 ms 356 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Incorrect 973 ms 5752 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 432 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Runtime error 62 ms 11000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -