oj.uz

Submission #637823

# Submission time Handle Problem Language Result Execution time Memory
637823 2022-09-03T11:32:31 Z Cross_Ratio Capital City (JOI20_capital_city) C++14
30 / 100
 275 ms 30604 KB 
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
int C[200005];
int ma[200005];
int mi[200005];
int A[200005];
int B[200005];
bool vis[200005];
int DnC(int s, int e, set<int> Col) {
    //cout << "DnC : " << s << ' ' << e << '\n';
    if(Col.size()==0 || e<=s) return 1e9;
    if(s+1==e && Col.find(B[s])!=Col.end()) return 0;
    //cout << "Possible Colors : ";
    //for(int n : Col) cout << n << ' ';
    //cout << '\n';
    int mid = (s+e)/2;
    int l = mid, r = mid;
    int pm = mi[B[mid]], pa = ma[B[mid]];
    int val = 1e9;
    if(Col.find(B[mid])!=Col.end()) {
        set<int> S;
        S.insert(B[mid]);
        bool isPos = true;
        while(pm < l || r < pa) {
            while(pm < l) {
                l--;
                if(Col.find(B[l])==Col.end()) {
                    isPos = false;
                    break;
                }
                S.insert(B[l]);
                pm = min(pm, mi[B[l]]);
                pa = max(pa, ma[B[l]]);
            }
            if(!isPos) break;
            while(r < pa) {
                r++;
                if(Col.find(B[r])==Col.end()) {
                    isPos = false;
                    break;
                }
                S.insert(B[r]);
                pm = min(pm, mi[B[r]]);
                pa = max(pa, ma[B[r]]);
            }
            if(!isPos) break;
        }
        if(isPos) val = min(val, (int)S.size()-1);
    }
    set<int> S1, S2;
    for(int n : Col) {
        if(s<=mi[n]&&ma[n]<mid) S1.insert(n);
        if(mid<mi[n]&&ma[n]<e) S2.insert(n);
    }
    //cout << val << '\n';
    val = min(val, DnC(s, mid, S1));
    val = min(val, DnC(mid+1, e, S2));
    //cout << s << " to " << e << " : " << val <<'\n';
    return val;
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, K;
    cin >> N >> K;
    int i, j;
    adj.resize(N);
    for(i=0;i<N-1;i++) {
        int a, b;
        cin >> a >> b;
        adj[a-1].push_back(b-1);
        adj[b-1].push_back(a-1);
    }
    int l = 0;
    vis[l] = true;
    while(true) {
        for(int n : adj[l]) {
            if(!vis[n]) {
                l = n;
                break;
            }
        }
        if(vis[l]) break;
        vis[l] = true;
    }
    for(i=0;i<N;i++) vis[i] = false;
    int cnt = 0;
    while(cnt < N) {
        A[cnt] = l;
        cnt++;
        vis[l] = true;
        for(int n : adj[l]) {
            if(!vis[n]) {
                l = n;
                break;
            }
        }
    }
    for(i=0;i<K;i++) {
        ma[i] = -1;
        mi[i] = N;
    }
    for(i=0;i<N;i++) {
        cin >> C[i];
        C[i]--;
    }
    for(i=0;i<N;i++) B[i] = C[A[i]];
    /*for(i=0;i<N;i++) cout << A[i] << ' ';
    cout <<'\n';
    for(i=0;i<N;i++) cout << B[i] << ' ';
    cout << '\n';*/
    for(i=0;i<N;i++) {
        ma[B[i]] = max(ma[B[i]], i);
        mi[B[i]] = min(mi[B[i]], i);
    }
    for(i=0;i<K;i++) {
        if(ma[i]==mi[i]) {
            cout << "0";
            return 0;
        }
    }
    set<int> col;
    for(i=0;i<K;i++) col.insert(i);
    cout << DnC(0, N, col);
}

Compilation message

capital_city.cpp: In function 'int main()':
capital_city.cpp:68:12: warning: unused variable 'j' [-Wunused-variable]
   68 |     int i, j;
      |            ^

Subtask #1
0 / 1.0

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

Subtask #2
0 / 10.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 24124 KB Output is correct
2 Correct 101 ms 27596 KB Output is correct
3 Correct 128 ms 27716 KB Output is correct
4 Correct 93 ms 27656 KB Output is correct
5 Correct 131 ms 29788 KB Output is correct
6 Correct 100 ms 28364 KB Output is correct
7 Correct 137 ms 30332 KB Output is correct
8 Correct 108 ms 30604 KB Output is correct
9 Correct 258 ms 29696 KB Output is correct
10 Correct 246 ms 29896 KB Output is correct
11 Correct 270 ms 29676 KB Output is correct
12 Correct 246 ms 29752 KB Output is correct
13 Correct 261 ms 29956 KB Output is correct
14 Correct 246 ms 29608 KB Output is correct
15 Correct 263 ms 29760 KB Output is correct
16 Correct 261 ms 29796 KB Output is correct
17 Correct 275 ms 30060 KB Output is correct
18 Correct 253 ms 29652 KB Output is correct
19 Correct 258 ms 29800 KB Output is correct
20 Correct 248 ms 29588 KB Output is correct
21 Correct 0 ms 340 KB Output is correct

Subtask #4
0 / 59.0

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