oj.uz

Submission #602074

# Submission time Handle Problem Language Result Execution time Memory
602074 2022-07-22T14:29:57 Z AA_Surely Capital City (JOI20_capital_city) C++14
31 / 100
 365 ms 37748 KB 
#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(int i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(int i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define WTF 		cout << "WTF" << endl

#define IOS 		ios::sync_with_stdio(false); cin.tie(0)
#define F 			first
#define S	 		second
#define pb 			push_back

#define ALL(x) 		x.begin(), x.end()
#define RALL(x) 	x.rbegin(), x.rend()

using namespace std;
typedef long long 		LL;

typedef pair<int, int> 	PII;
typedef pair<LL, LL> 	PLL;

typedef vector<int> 	VI;
typedef vector<LL> 		VLL;
typedef vector<PII> 	VPII;
typedef vector<PLL> 	VPLL;

const int N = 2e5 + 7;
const int ALPHA = 27;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int LOG = 22;

int n, k, vcnt;
int eset[N][2], ns[N];
int comp[N], par[N], sz[N];
bool valid[N], vis[N];
VI adj[N], rs, group[N];

void init() {
    cin >> n >> k;
    F0R(i, n - 1) {
        cin >> eset[i][0] >> eset[i][1];
        eset[i][0]--; eset[i][1]--;
    }

    F0R(i, n) {
        cin >> ns[i];
        ns[i]--;
        group[ ns[i] ].pb(i);
    }

    fill(valid, valid + k, 1);
    vcnt = k;
    return;
}

void preD(int now, int c) {
    vis[now] = 1;
    comp[now] = c;

    for(int on : adj[now]) if (!vis[on]) preD(on, c);
    return;
}

bool buildGraph() {
    F0R(i, n) adj[i].clear();
    rs.clear();

    F0R(i, n - 1) {
        if (valid[ ns[ eset[i][0] ] ] && valid[ ns[ eset[i][1] ] ]) {
            adj[ eset[i][0] ].pb(eset[i][1]);
            adj[ eset[i][1] ].pb(eset[i][0]);
        }
    }
    
    memset(vis, 0, sizeof vis);

    int c = 0;
    F0R(i, n) if (!vis[i]) {
        rs.pb(i);
        preD(i, c);
        c++;
    }
    
    F0R(i, k) {
        FOR(j, 1, group[i].size()) {
            if (valid[i] && comp[ group[i][j] ] != comp[ group[i][j - 1] ]) {
                vcnt--;
                valid[i] = 0;
            }
        }
    }

    return 1;
}

int getSz(int now, int p) {
    sz[now] = 1;
    for(int on : adj[now]) if (on != p) sz[now] += getSz(on, now);
    return sz[now];
}

int getCent(int now, int p, int s) {
    for(int on : adj[now]) if (on != p) 
        if (sz[on] > (s / 2)) return getCent(on, now, s);
    return now;
}

void getPar(int now, int p) {
    par[now] = p;
    for(int on : adj[now]) if (on != p) getPar(on, now);
    return;
}

int solve(int root) {
    getSz(root, -1);
    int c = getCent(root, -1, sz[root]);
    getPar(c, -1);

    int ret = 0;
    if (!valid[ ns[c] ]) return INF;

    queue<int> keep;
    keep.push(ns[c]);
    assert(!vis[ ns[c] ]);
    vis[ ns[c] ] = 1;

    while(!keep.empty()) {
        int now = keep.front();
        keep.pop();

        for(int on : group[now]) {
            int p = par[on];
            if (p == -1) continue;
            if (!valid[ ns[p] ]) return INF;
            if (!vis[ ns[p] ]) {
                keep.push(ns[p]);
                vis[ ns[p] ] = 1;
                ret++;
            }
        }
    }
    
    if (valid[ ns[c] ]) vcnt--;
    valid[ ns[c] ] = 0;

    return ret;
}

int main() {
    IOS;
    
    init();

    int ans = INF;
    int cc = 0;
    while(buildGraph() && vcnt) {
        cc++;
        assert(cc <= 100);
        memset(vis, 0, sizeof vis);
        for(const int &on : rs)
            ans = min(ans, solve(on));
    }
    
    cout << ans;
}

Compilation message

capital_city.cpp: In function 'bool buildGraph()':
capital_city.cpp:3:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i,x,n)  for(int i=x; i<n; i++)
......
   88 |         FOR(j, 1, group[i].size()) {
      |             ~~~~~~~~~~~~~~~~~~~~~  
capital_city.cpp:88:9: note: in expansion of macro 'FOR'
   88 |         FOR(j, 1, group[i].size()) {
      |         ^~~

Subtask #1
1.0 / 1.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 8 ms 9940 KB Output is correct
3 Correct 6 ms 9940 KB Output is correct
4 Correct 8 ms 9940 KB Output is correct
5 Correct 7 ms 9940 KB Output is correct
6 Correct 7 ms 9940 KB Output is correct
7 Correct 7 ms 9940 KB Output is correct
8 Correct 8 ms 9828 KB Output is correct
9 Correct 6 ms 9940 KB Output is correct
10 Correct 7 ms 9812 KB Output is correct
11 Correct 9 ms 10068 KB Output is correct
12 Correct 7 ms 10068 KB Output is correct
13 Correct 8 ms 10004 KB Output is correct
14 Correct 7 ms 10088 KB Output is correct
15 Runtime error 32 ms 20352 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 36208 KB Output is correct
2 Correct 100 ms 36556 KB Output is correct
3 Correct 211 ms 35952 KB Output is correct
4 Correct 104 ms 36576 KB Output is correct
5 Correct 273 ms 34680 KB Output is correct
6 Correct 115 ms 37748 KB Output is correct
7 Correct 228 ms 34912 KB Output is correct
8 Correct 100 ms 37340 KB Output is correct
9 Correct 336 ms 33320 KB Output is correct
10 Correct 308 ms 31252 KB Output is correct
11 Correct 276 ms 33728 KB Output is correct
12 Correct 352 ms 35756 KB Output is correct
13 Correct 276 ms 30980 KB Output is correct
14 Correct 365 ms 35932 KB Output is correct
15 Correct 292 ms 35736 KB Output is correct
16 Correct 307 ms 31724 KB Output is correct
17 Correct 324 ms 32116 KB Output is correct
18 Correct 261 ms 32308 KB Output is correct
19 Correct 346 ms 34920 KB Output is correct
20 Correct 298 ms 36672 KB Output is correct
21 Correct 5 ms 9940 KB Output is correct

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 8 ms 9940 KB Output is correct
3 Correct 6 ms 9940 KB Output is correct
4 Correct 8 ms 9940 KB Output is correct
5 Correct 7 ms 9940 KB Output is correct
6 Correct 7 ms 9940 KB Output is correct
7 Correct 7 ms 9940 KB Output is correct
8 Correct 8 ms 9828 KB Output is correct
9 Correct 6 ms 9940 KB Output is correct
10 Correct 7 ms 9812 KB Output is correct
11 Correct 9 ms 10068 KB Output is correct
12 Correct 7 ms 10068 KB Output is correct
13 Correct 8 ms 10004 KB Output is correct
14 Correct 7 ms 10088 KB Output is correct
15 Runtime error 32 ms 20352 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -