제출 #861944

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
861944		sleepntsheep	Museum (CEOI17_museum)	C++17	0 / 100	377 ms	1048576 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][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;
}

컴파일 시 표준 에러 (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)
      |                                     ~~~~~~~~~~~~^~~

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