Submission #541260

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
541260	2022-03-22T20:44:24 Z	rainliofficial	Museum (CEOI17_museum)	Java 11	Compilation error	0 ms	0 KB

museum

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define f first
#define s second

/**
 * The challenge of the problem is to know which edges we want to "backtrack" on (meaning we pass an edge twice). 
 * It is key that we realize the given graph is a tree, which means we can use tree DP. 
 * 
 * Let dp[i][j][0/1] = the min cost to visit j nodes in subtree of i, such that 0 = we don't return back to i, 1 = we return back to i
 */

struct edge{
    int to, c;
};

const int MAXN = 10001;
int n, k, x, ss[MAXN], dp[MAXN][MAXN][2], dp2[MAXN][MAXN][2];
vector<edge> arr[MAXN];

void subtreeSize(int at, int par){
    ss[at] = 1;
    for (edge i : arr[at]){
        if (i.to != par){
            subtreeSize(i.to, at);
            ss[at] += ss[i.to];
        }
    }
}

void dfs(int at, int par){
    // try to "tack on" the answer of the children of at
    int currSize = 1; 
    for (edge i : arr[at]){
        if (i.to != par){
            dfs(i.to, at);
            // combine the new subtree with the existing subtree of at
            for (int atSize=1; atSize<=currSize; atSize++){
                for (int newSize=1; newSize<=ss[i.to]; newSize++){
                    dp2[at][atSize + newSize][0] = min({dp2[at][atSize + newSize][0], dp[at][atSize][1] + dp[i.to][newSize][0] + i.c, dp[at][atSize][0] + dp[i.to][newSize][1] + 2*i.c});
                    dp2[at][atSize + newSize][1] = min(dp2[at][atSize + newSize][1], dp[at][atSize][1] + dp[i.to][newSize][1] + 2*i.c);
                }
            }
            // copy over data
            for (int atSize=1; atSize<=currSize; atSize++){
                for (int newSize=1; newSize<=ss[i.to]; newSize++){
                    dp[at][atSize + newSize][0] = min(dp[at][atSize + newSize][0], dp2[at][atSize + newSize][0]);
                    dp[at][atSize + newSize][1] = min(dp[at][atSize + newSize][1], dp2[at][atSize + newSize][1]);
                }
            }
            for (int atSize=1; atSize<=currSize; atSize++){
                for (int newSize=1; newSize<=ss[i.to]; newSize++){
                    dp2[at][atSize + newSize][0] = dp2[at][atSize + newSize][1] = INT_MAX;
                    
                }
            }
            currSize += ss[i.to];
        }
    }
}
int main(){
    cin.tie(0); ios_base::sync_with_stdio(0);
    // freopen("file.in", "r", stdin);
    // freopen("file.out", "w", stdout);
    cin >> n >> k >> x;
    x--;
    for (int i=0; i<n-1; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        arr[a].push_back({b, c});
        arr[b].push_back({a, c});
    }
    for (int i=0; i<MAXN; i++){
        for (int j=0; j<MAXN; j++){
            if (j > 1){
                dp[i][j][0] = dp[i][j][1] = INT_MAX;
            }
            dp2[i][j][0] = dp2[i][j][1] = INT_MAX;
        }
    }
    subtreeSize(x, -1);
    dfs(x, -1);
    cout << dp[x][k][0] << "\n";
}

Compilation message

museum.java:1: error: illegal character: '#'
#include <bits/stdc++.h>
^
museum.java:1: error: class, interface, or enum expected
#include <bits/stdc++.h>
         ^
museum.java:3: error: illegal character: '#'
#define ll long long
^
museum.java:3: error: class, interface, or enum expected
#define ll long long
        ^
museum.java:4: error: illegal character: '#'
#define pii pair<int, int>
^
museum.java:5: error: illegal character: '#'
#define sz(x) (int)x.size()
^
museum.java:6: error: illegal character: '#'
#define f first
^
museum.java:7: error: illegal character: '#'
#define s second
^
museum.java:18: error: class, interface, or enum expected
};
^
museum.java:20: error: class, interface, or enum expected
const int MAXN = 10001;
^
museum.java:21: error: class, interface, or enum expected
int n, k, x, ss[MAXN], dp[MAXN][MAXN][2], dp2[MAXN][MAXN][2];
^
museum.java:22: error: class, interface, or enum expected
vector<edge> arr[MAXN];
^
museum.java:24: error: class, interface, or enum expected
void subtreeSize(int at, int par){
^
museum.java:26: error: class, interface, or enum expected
    for (edge i : arr[at]){
    ^
museum.java:29: error: class, interface, or enum expected
            ss[at] += ss[i.to];
            ^
museum.java:30: error: class, interface, or enum expected
        }
        ^
museum.java:37: error: class, interface, or enum expected
    for (edge i : arr[at]){
    ^
museum.java:41: error: class, interface, or enum expected
            for (int atSize=1; atSize<=currSize; atSize++){
            ^
museum.java:41: error: class, interface, or enum expected
            for (int atSize=1; atSize<=currSize; atSize++){
                               ^
museum.java:41: error: class, interface, or enum expected
            for (int atSize=1; atSize<=currSize; atSize++){
                                                 ^
museum.java:42: error: class, interface, or enum expected
                for (int newSize=1; newSize<=ss[i.to]; newSize++){
                                    ^
museum.java:42: error: class, interface, or enum expected
                for (int newSize=1; newSize<=ss[i.to]; newSize++){
                                                       ^
museum.java:44: error: class, interface, or enum expected
                    dp2[at][atSize + newSize][1] = min(dp2[at][atSize + newSize][1], dp[at][atSize][1] + dp[i.to][newSize][1] + 2*i.c);
                    ^
museum.java:45: error: class, interface, or enum expected
                }
                ^
museum.java:48: error: class, interface, or enum expected
            for (int atSize=1; atSize<=currSize; atSize++){
                               ^
museum.java:48: error: class, interface, or enum expected
            for (int atSize=1; atSize<=currSize; atSize++){
                                                 ^
museum.java:49: error: class, interface, or enum expected
                for (int newSize=1; newSize<=ss[i.to]; newSize++){
                                    ^
museum.java:49: error: class, interface, or enum expected
                for (int newSize=1; newSize<=ss[i.to]; newSize++){
                                                       ^
museum.java:51: error: class, interface, or enum expected
                    dp[at][atSize + newSize][1] = min(dp[at][atSize + newSize][1], dp2[at][atSize + newSize][1]);
                    ^
museum.java:52: error: class, interface, or enum expected
                }
                ^
museum.java:54: error: class, interface, or enum expected
            for (int atSize=1; atSize<=currSize; atSize++){
                               ^
museum.java:54: error: class, interface, or enum expected
            for (int atSize=1; atSize<=currSize; atSize++){
                                                 ^
museum.java:55: error: class, interface, or enum expected
                for (int newSize=1; newSize<=ss[i.to]; newSize++){
                                    ^
museum.java:55: error: class, interface, or enum expected
                for (int newSize=1; newSize<=ss[i.to]; newSize++){
                                                       ^
museum.java:58: error: class, interface, or enum expected
                }
                ^
museum.java:61: error: class, interface, or enum expected
        }
        ^
museum.java:65: error: class, interface, or enum expected
    cin.tie(0); ios_base::sync_with_stdio(0);
                ^
museum.java:68: error: class, interface, or enum expected
    cin >> n >> k >> x;
    ^
museum.java:69: error: class, interface, or enum expected
    x--;
    ^
museum.java:70: error: class, interface, or enum expected
    for (int i=0; i<n-1; i++){
    ^
museum.java:70: error: class, interface, or enum expected
    for (int i=0; i<n-1; i++){
                  ^
museum.java:70: error: class, interface, or enum expected
    for (int i=0; i<n-1; i++){
                         ^
museum.java:72: error: class, interface, or enum expected
        cin >> a >> b >> c;
        ^
museum.java:73: error: class, interface, or enum expected
        a--; b--;
        ^
museum.java:73: error: class, interface, or enum expected
        a--; b--;
             ^
museum.java:74: error: class, interface, or enum expected
        arr[a].push_back({b, c});
        ^
museum.java:75: error: class, interface, or enum expected
        arr[b].push_back({a, c});
        ^
museum.java:76: error: class, interface, or enum expected
    }
    ^
museum.java:77: error: class, interface, or enum expected
    for (int i=0; i<MAXN; i++){
                  ^
museum.java:77: error: class, interface, or enum expected
    for (int i=0; i<MAXN; i++){
                          ^
museum.java:78: error: class, interface, or enum expected
        for (int j=0; j<MAXN; j++){
                      ^
museum.java:78: error: class, interface, or enum expected
        for (int j=0; j<MAXN; j++){
                              ^
museum.java:81: error: class, interface, or enum expected
            }
            ^
museum.java:83: error: class, interface, or enum expected
        }
        ^
museum.java:86: error: class, interface, or enum expected
    dfs(x, -1);
    ^
museum.java:87: error: class, interface, or enum expected
    cout << dp[x][k][0] << "\n";
    ^
museum.java:88: error: class, interface, or enum expected
}
^
57 errors