Submission #221947

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
221947	2020-04-11T15:00:05 Z	Haunted_Cpp	Džumbus (COCI19_dzumbus)	C++17	Compilation error	0 ms	0 KB

dzumbus

/*
 author: Haunted_Cpp
*/

#include <cstdio>
#include <algorithm>

#pragma GCC optimize ("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

using namespace std;

const int N = 1e3 + 5;
const int DUMMY = 0;
const long long INF = 1e15 + 5;

long long dp [N][N][2];
long long cost [N];

int sub [N];

vector<int> g [N];

bool vis [N];

void join (int node, int p = -1) {
  vis[node] = true;
  for (auto to : g[node]) {
    if (!vis[to]) {
      vis[to] = true;
      join (to, node);
    }
  }
}

// DP[NODE][SCORE][IS_VALID]
// IS_VALID - denotes if the connected component ending at node i has 2 or more nodes

void dfs (int node = 0, int p = -1) { 
  dp[node][0][0] = 0;
  sub[node] = 1;
  for (auto to : g[node]) {
    if (to == p) continue;
    dfs (to, node);
    sub[node] += sub[to];
    // USE
    for (int i = sub[node]; i >= 2; i--) {
      for (int j = i; j >= 0; j--) {
        dp[node][i][1] = min (dp[node][i][1], dp[node][i - j][1] + dp[to][j][1]);
        dp[node][i][1] = min (dp[node][i][1], dp[node][i - j][1] + dp[to][j][0]);
        if (i - j - 1 >= 0 && j - 1 >= 0) { 
          dp[node][i][1] = min (dp[node][i][1], dp[node][i - j - 1][0] + cost[node] + dp[to][j - 1][0] + cost[to]);
        }
        if (j - 1 >= 0) {
          dp[node][i][1] = min (dp[node][i][1], dp[node][i - j][1] + dp[to][j - 1][0] + cost[to]);
        }
        if (i - j - 1 >= 0) {
           dp[node][i][1] = min (dp[node][i][1], dp[node][i - j - 1][0] + cost[node] + dp[to][j][1]);
         }
      }
    }  
    // NOT USE
    for (int i = sub[node]; i >= 2; i--) {
      for (int j = i; j >= 0; j--) {
        dp[node][i][0] = min (dp[node][i][0], dp[node][i - j][0] + min (dp[to][j][0], dp[to][j][1]));
      }
    }
  }
}

int main () {
  int n, m;
  scanf ("%d %d", &n, &m);
  cost[0] = INF;
  for (int i = 1; i <= n; i++) scanf ("%lld", &cost[i]);
  for (int i = 0; i < m; i++) {
    int st, et;
    scanf ("%d %d", &st, &et);
    g[st].emplace_back(et);
    g[et].emplace_back(st);
  }
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      g[DUMMY].emplace_back(i);
      join (i);
    }
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      dp[i][j][0] = dp[i][j][1] = INF;
    }
  }
  dfs ();
  int q;
  scanf ("%d", &q);
  vector<pair<int, int> > perguntas (q);
  for (int i = 0; i < q; i++) {
    scanf ("%d", &perguntas[i].first);
    perguntas[i].second = i;
  }
  sort (perguntas.begin(), perguntas.end());
  vector<pair<long long, int> > Get (N);
  for (int i = 0; i < N; i++) {
    Get[i] = {dp[0][i][0], i};
  }
  sort (Get.begin(), Get.begin() + n + 1);
  int pergunta_atual = 0;
  int mx = 0;
  vector<int> ans (q);
  for (int i = 0; i < q; i++) {
    while (pergunta_atual < N && Get[pergunta_atual].first <= perguntas[i].first) {
      mx = max (mx, Get[pergunta_atual].second);
      ++pergunta_atual;
    }
    ans[perguntas[i].second] = mx;
  }
  for (int i = 0; i < q; i++) printf ("%d\n", ans[i]);
  return 0;
}

Compilation message

dzumbus.cpp:23:1: error: 'vector' does not name a type; did you mean 'qecvt_r'?
 vector<int> g [N];
 ^~~~~~
 qecvt_r
dzumbus.cpp: In function 'void join(int, int)':
dzumbus.cpp:29:18: error: 'g' was not declared in this scope
   for (auto to : g[node]) {
                  ^
dzumbus.cpp: In function 'void dfs(int, int)':
dzumbus.cpp:43:18: error: 'g' was not declared in this scope
   for (auto to : g[node]) {
                  ^
dzumbus.cpp: In function 'int main()':
dzumbus.cpp:80:5: error: 'g' was not declared in this scope
     g[st].emplace_back(et);
     ^
dzumbus.cpp:85:7: error: 'g' was not declared in this scope
       g[DUMMY].emplace_back(i);
       ^
dzumbus.cpp:97:3: error: 'vector' was not declared in this scope
   vector<pair<int, int> > perguntas (q);
   ^~~~~~
dzumbus.cpp:97:3: note: suggested alternative: 'qecvt_r'
   vector<pair<int, int> > perguntas (q);
   ^~~~~~
   qecvt_r
dzumbus.cpp:97:25: error: expected primary-expression before '>' token
   vector<pair<int, int> > perguntas (q);
                         ^
dzumbus.cpp:97:27: error: 'perguntas' was not declared in this scope
   vector<pair<int, int> > perguntas (q);
                           ^~~~~~~~~
dzumbus.cpp:103:31: error: expected primary-expression before '>' token
   vector<pair<long long, int> > Get (N);
                               ^
dzumbus.cpp:103:33: error: 'Get' was not declared in this scope
   vector<pair<long long, int> > Get (N);
                                 ^~~
dzumbus.cpp:103:33: note: suggested alternative: 'getw'
   vector<pair<long long, int> > Get (N);
                                 ^~~
                                 getw
dzumbus.cpp:110:10: error: expected primary-expression before 'int'
   vector<int> ans (q);
          ^~~
dzumbus.cpp:116:5: error: 'ans' was not declared in this scope
     ans[perguntas[i].second] = mx;
     ^~~
dzumbus.cpp:116:5: note: suggested alternative: 'abs'
     ans[perguntas[i].second] = mx;
     ^~~
     abs
dzumbus.cpp:118:47: error: 'ans' was not declared in this scope
   for (int i = 0; i < q; i++) printf ("%d\n", ans[i]);
                                               ^~~
dzumbus.cpp:118:47: note: suggested alternative: 'abs'
   for (int i = 0; i < q; i++) printf ("%d\n", ans[i]);
                                               ^~~
                                               abs
dzumbus.cpp:74:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d", &n, &m);
   ~~~~~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:76:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 1; i <= n; i++) scanf ("%lld", &cost[i]);
                                ~~~~~~^~~~~~~~~~~~~~~~~~
dzumbus.cpp:79:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &st, &et);
     ~~~~~~^~~~~~~~~~~~~~~~~~~
dzumbus.cpp:96:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", &q);
   ~~~~~~^~~~~~~~~~