Submission #861942

#	Time	Username	Problem	Language	Result	Execution time	Memory
861942		sleepntsheep	Museum (CEOI17_museum)	C++17	0 / 100	328 ms	785148 KiB

museum

#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];

/*
 * 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;
}

ll 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, -1, sizeof dp);



    return 0;
}

Compilation message (stderr)

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)
      |                                     ~~~~~~~~~~~~^~~
museum.cpp: In function 'll dfs(int, int)':
museum.cpp:56:1: warning: no return statement in function returning non-void [-Wreturn-type]
   56 | }
      | ^

• Subtask 1: 0 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20