oj.uz

Submission #922506

# Submission time Handle Problem Language Result Execution time Memory
922506 2024-02-05T15:13:20 Z cpptowin Museum (CEOI17_museum) C++17
80 / 100
 434 ms 1048576 KB 
#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
#define int long long
#define inf 1000000000
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(1<<j))
#define vi vector<int>
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}
using namespace std;
int n,k,x;
vii ke[maxn];
int f[10001][10001][2];
int sz[maxn];
void dfs(int u,int parent)
{
    sz[u] = 1;
    for(auto [v,w] : ke[u])
    {
        if(v == parent) continue;
        dfs(v,u);
        sz[u] += sz[v];
        fod(i,sz[u],2) fo(j,max(0LL,i - sz[u] + sz[v]),min(i,sz[v])) 
        {
            f[u][i][0] = min(f[u][i][0],f[v][j][1] + f[u][i - j][0] + 2 * w);
            f[u][i][0] = min(f[u][i][0],f[v][j][0] + f[u][i - j][1] + w);
            f[u][i][1] = min(f[u][i][1],f[v][j][1] + f[u][i - j][1] + 2 * w);
        }
    }
}
main()
{
    #define name "TASK"
    if(fopen(name".inp","r"))
    {
       freopen(name".inp","r",stdin);
       freopen(name".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n >> k >> x;
    fo(i,1,n - 1)
    {
        int u,v,w;
        cin >> u >> v >> w;
        ke[u].pb(v,w);
        ke[v].pb(u,w);
    }
    fo(i,1,n) fo(j,2,k) f[i][j][0] = f[i][j][1] = inf;
    dfs(x,x);
    cout << f[x][k][0];
}

Compilation message

museum.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   42 | main()
      | ^~~~
museum.cpp: In function 'int main()':
museum.cpp:47:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |        freopen(name".inp","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
museum.cpp:48:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |        freopen(name".out","w",stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31576 KB Output is correct
2 Correct 7 ms 31580 KB Output is correct
3 Correct 7 ms 31580 KB Output is correct
4 Correct 7 ms 31580 KB Output is correct
5 Correct 7 ms 31580 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 372872 KB Output is correct
2 Correct 167 ms 373616 KB Output is correct
3 Correct 390 ms 584000 KB Output is correct
4 Correct 232 ms 438612 KB Output is correct
5 Correct 182 ms 389200 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 372872 KB Output is correct
2 Correct 167 ms 373616 KB Output is correct
3 Correct 390 ms 584000 KB Output is correct
4 Correct 232 ms 438612 KB Output is correct
5 Correct 182 ms 389200 KB Output is correct
6 Correct 171 ms 377940 KB Output is correct
7 Correct 289 ms 504728 KB Output is correct
8 Correct 392 ms 383144 KB Output is correct
9 Correct 315 ms 383180 KB Output is correct
10 Correct 189 ms 382296 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31576 KB Output is correct
2 Correct 7 ms 31580 KB Output is correct
3 Correct 7 ms 31580 KB Output is correct
4 Correct 7 ms 31580 KB Output is correct
5 Correct 7 ms 31580 KB Output is correct
6 Correct 191 ms 372872 KB Output is correct
7 Correct 167 ms 373616 KB Output is correct
8 Correct 390 ms 584000 KB Output is correct
9 Correct 232 ms 438612 KB Output is correct
10 Correct 182 ms 389200 KB Output is correct
11 Correct 171 ms 377940 KB Output is correct
12 Correct 289 ms 504728 KB Output is correct
13 Correct 392 ms 383144 KB Output is correct
14 Correct 315 ms 383180 KB Output is correct
15 Correct 189 ms 382296 KB Output is correct
16 Correct 213 ms 490508 KB Output is correct
17 Correct 434 ms 997860 KB Output is correct
18 Correct 296 ms 559200 KB Output is correct
19 Correct 383 ms 495952 KB Output is correct
20 Correct 234 ms 495448 KB Output is correct
21 Runtime error 360 ms 1048576 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -