oj.uz

Submission #105958

# Submission time Handle Problem Language Result Execution time Memory
105958 2019-04-16T01:19:29 Z TuGSGeReL Friend (IOI14_friend) C++14
0 / 100
 820 ms 5400 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[]){
     
     
      for (int i = 0; i < n; i++)
      {
        p[i].ff = ++idx;
        fl[0][idx] = 1;
        p[i].ss = ++idx;
        fl[p[i].ff][p[i].ss] = fl[p[i].ss][p[i].ff] = 1;
      }	
      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] = fl[p[i].ff][p[host[i]].ss] = 1;
        } else {
          for (auto x : edg[host[i]])
          {
            fl[p[x].ss][p[i].ff] = fl[p[i].ff][p[x].ss] = 1;
            edg[x].pub(i);
            edg[i].pub(x);
          }
        }
      }
      for (int i = 0; i <= idx; i++)
        fl[p[i].ss][idx + 1] = fl[idx + 1][p[i].ss] = 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:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           for (int j = 0; j < edg[host[i]].size(); j++)
                           ~~^~~~~~~~~~~~~~~~~~~~~
friend.cpp:46:29: 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:12: warning: variable 'boo' set but not used [-Wunused-but-set-variable]
       bool boo = 1;
            ^~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 2224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 820 ms 5400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -