oj.uz

Submission #861944

# Submission time Handle Problem Language Result Execution time Memory
861944 2023-10-17T08:49:42 Z sleepntsheep Museum (CEOI17_museum) C++17
0 / 100
 377 ms 1048576 KB 
#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)

#define N 10002
#define ALL(x) x.begin(), x.end()

int dp[N*2][N][2];

/*
 * state: dp[u][i] = at u-th room, visited i room
 * 
 * transition: 
 *      dp[u][i] = min(dp[v1][i-1] + 2*w1, dp[v2][i-1] + 2*w2, min 1 <= k < i-1 (dp[v1][k] + dp[v2][i-1-k] + 2*w1 + 2*w2))
 */

int n, k, x;
vector<vector<pair<int, int>>> g;

vector<vector<pair<int, int>>> binarize(vector<vector<pair<int, int>>> g)
{
    int nn = g.size();
    vector<vector<pair<int, int>>> rg(nn);
    for (int i = 0; i < g.size(); ++i)
    {
        if (g[i].size() > 2)
        {
            for (int j = 0, at = i; g[i].size() > j; ++j)
            {
                int new_node = nn++;
                rg.resize(nn);
                rg[at] = {g[i][j], {0, new_node}};
                at = new_node;
            }
        }
        else
            rg[i] = g[i];
    }
    return rg;
}

void dfs(int u, int p)
{
}

int main()
{
    ShinLena;
    cin >> n >> k >> x;
    g.resize(n+1);
    for (int i = 1, u, v, w; i < n; ++i)
        cin >> u >> v >> w, g[u].emplace_back(w, v), g[v].emplace_back(w, u);
    g = binarize(g);
    memset(dp, 63, sizeof dp);

    return 0;
}

Compilation message

museum.cpp: In function 'std::vector<std::vector<std::pair<int, int> > > binarize(std::vector<std::vector<std::pair<int, int> > >)':
museum.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 0; i < g.size(); ++i)
      |                     ~~^~~~~~~~~~
museum.cpp:40:49: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |             for (int j = 0, at = i; g[i].size() > j; ++j)
      |                                     ~~~~~~~~~~~~^~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 377 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 320 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 320 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 377 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -