oj.uz

Submission #50803

# Submission time Handle Problem Language Result Execution time Memory
50803 2018-06-13T11:12:49 Z Just_Solve_The_Problem Friend (IOI14_friend) C++11
19 / 100
 1000 ms 147456 KB 
#include <bits/stdc++.h>
#include "friend.h"

using namespace std;

#define pb push_back
#define sz(s) (int)s.size()
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define all(s) s.begin(), s.end()

const int N = (int)1e5 + 7;
const int smN = (int)1e3 + 7;

vector < int > gr[N];
int has[smN][smN];
int c[N], dp[N], used[N];

void addedge(int a, int b) {
  gr[a].pb(b);
  gr[b].pb(a);
  has[a][b] = has[b][a] = 1;
}

void dfs(int v, int pr) {
  used[v] = 1;
  int res = 0;
  int res1 = 0;
  for (int to : gr[v]) {
    if (to == pr) continue;
    dfs(to, v);
    for (int tto : gr[to]) {
      if (tto == v) continue;
      res += dp[tto];
    }
    res1 += dp[to];
  }
  dp[v] = max(dp[v], res1);
  dp[v] = max(dp[v], res + c[v]);
}


int findSample(int n, int confidence[], int host[], int protocol[]){
  for (int i = 0; i < n; i++) c[i] = confidence[i];
  int ans = 0;
  for (int i = 1; i < n; i++) {
    if (protocol[i] == 0 || protocol[i] == 2) {
      addedge(host[i], i);
    }
    if (protocol[i] == 1 || protocol[i] == 2) {
      for (int to : gr[host[i]]) {
        addedge(to, i);
      }
    }
  }
  int st = -1;
  for (int i = 0; i < n; i++) {
    if (sz(gr[i]) == 1 && st == -1) st = i;
  }
  assert(st != -1);
  for (int i = 0; i < n; i++) {
    memset(dp, 0, sizeof dp);
    dfs(i, i);
    ans = max(ans, dp[i]);
  }
  return ans;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 4 ms 3176 KB Output is correct
3 Correct 4 ms 3356 KB Output is correct
4 Correct 4 ms 3356 KB Output is correct
5 Correct 4 ms 3356 KB Output is correct
6 Correct 4 ms 3356 KB Output is correct
7 Execution timed out 1036 ms 147456 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 147456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 147456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 147456 KB Output is correct
2 Correct 6 ms 147456 KB Output is correct
3 Correct 4 ms 147456 KB Output is correct
4 Correct 5 ms 147456 KB Output is correct
5 Correct 47 ms 147456 KB Output is correct
6 Correct 40 ms 147456 KB Output is correct
7 Correct 8 ms 147456 KB Output is correct
8 Correct 42 ms 147456 KB Output is correct
9 Correct 5 ms 147456 KB Output is correct
10 Correct 17 ms 147456 KB Output is correct
11 Correct 19 ms 147456 KB Output is correct
12 Correct 38 ms 147456 KB Output is correct
13 Correct 35 ms 147456 KB Output is correct
14 Correct 8 ms 147456 KB Output is correct
15 Correct 42 ms 147456 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 147456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 147456 KB Output is correct
2 Correct 4 ms 147456 KB Output is correct
3 Execution timed out 1075 ms 147456 KB Time limit exceeded
4 Halted 0 ms 0 KB -