oj.uz

Submission #1104958

# Submission time Handle Problem Language Result Execution time Memory
1104958 2024-10-25T00:49:45 Z hiensumi Capital City (JOI20_capital_city) C++14
1 / 100
 56 ms 16212 KB 
#include <bits/stdc++.h>
using namespace std;
#define fod(i,a,b) for(int i((int) (a)), _b(b); i <= _b; i++)
#define fok(i,a,b) for(int i((int) (a)), _b(b); i >= _b; i--)
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define ve vector
#define vi ve<int>
#define vll ve<ll>
#define el '\n'
#define mask(i) (1LL<<(i))
#define BIT(msk,i) (msk>>(i)&1LL)
template<class T> bool mini(T &a, T b){ return (a > (b) ? a = (b), 1 : 0); }
template<class T> bool maxi(T &a, T b){ return (a < (b) ? a = (b), 1 : 0); }
const int base = mask(20) + 5;
#define name "capital"

int n, k;
ve <vi> g;

const int N = 2e5;

int city[N + 5], sz[N + 5];

namespace sub1{
    bool check(){
        return n <= 20;
    }

    bool vst[25];

    void dfs(int u, int p, int msk){
        if(!BIT(msk, city[u] - 1)) return;
        vst[u] = 1;

        for(int v : g[u]) if(v != p) dfs(v, u, msk);
    }

    void solve(){
        int res = 1e9;
        fod(msk,1,mask(k) - 1){
            fod(i,1,n) vst[i] = 0;

            int x = 0;

            fod(i,1,n) if(BIT(msk, city[i] - 1)){
                x = i;
                break;
            }

            dfs(x, 0, msk);

            bool ok = 1;
            fod(i,1,n) if(BIT(msk, city[i] - 1)){
                ok &= vst[i];
            }

            if(ok) mini(res, __builtin_popcount(msk) - 1);
        }

        cout << res;
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    if(fopen(name".inp", "r")){
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    cin >> n >> k;

    g.resize(n + 1);
    fod(i,1,n-1){
        int u, v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    fod(i,1,n){
        cin >> city[i], sz[city[i]]++;
    }

    if(sub1 :: check()) sub1 :: solve();

    return 0;
}

Compilation message

capital_city.cpp: In function 'int main()':
capital_city.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Incorrect 2 ms 592 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 16212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Incorrect 2 ms 592 KB Output isn't correct
12 Halted 0 ms 0 KB -