oj.uz

Submission #303938

# Submission time Handle Problem Language Result Execution time Memory
303938 2020-09-20T19:47:35 Z fivefourthreeone Towns (IOI15_towns) C++17
100 / 100
 22 ms 896 KB 
    #include "towns.h"
    #include <bits/stdc++.h>
     
    using namespace std;
     
    const int mxN = 111;
    int arr[mxN];
    int dist[mxN][mxN];
    int numHub = 0;
    int lcadist[mxN];
    int n;
    int s, t;
    int getdist(int a, int b) {
        if(a==b)return 0;
        if(dist[a][b]==-1) {
            return dist[a][b] = dist[b][a] = getDistance(a, b);
        }
        return dist[a][b];
    }
    bool solve(int hub) {
        //cout<<hub<<" "<<lcadist[hub]<<"\n";
        vector<int> stk;
        vector<int> bkt;
        int pre = 0;
        int post = 0;
        vector<int> ch;
        for(int i = 0; i < n; ++i) {
            if(lcadist[i] > lcadist[hub])post++;
            else if(lcadist[i] < lcadist[hub])pre++;
            else ch.push_back(i);
        }
        function<bool(int, int)> compare = [&](int a, int b) {
            //cout<<a<<" "<<b<<" "<<lcadist[a]<<" "<<lcadist[b]<<" "<<lcadist[hub]<<"\n";
            if(lcadist[a] < lcadist[hub] && lcadist[b] < lcadist[hub]) {
                return true;
            }else if(lcadist[a] > lcadist[hub] && lcadist[b] > lcadist[hub]) {
                return true;   
            }else if(lcadist[a] == lcadist[hub] && lcadist[b] == lcadist[hub]) {
                if(getdist(s, a) + getdist(s, b) - getdist(a, b) > 2 * lcadist[hub])return true;
            }
            return false;
        };
        //cout<<post<<" "<<pre<<"\n";
        if(max(post, pre) > n/2) return false;
        if(ch.size() <= n/2) return true;
        for(int i: ch) {
            if(stk.empty()) {
                stk.push_back(i);
            }else if(!compare(stk.back(), i)) {
                //cout<<stk.back()<<" "<<i<<"\n";
                stk.push_back(i);
                if(bkt.size()) {
                    stk.push_back(bkt.back());
                    bkt.pop_back();
                }
            }else {
                bkt.push_back(i);
            }
        }
        int T = stk.back();
        while(stk.size()) {
            if(!compare(stk.back(), T)) {
                //cout<<T<<" "<<stk.back()<<"\n";
                stk.pop_back();
                if(bkt.size()) bkt.pop_back();
                else break;
            }else {
                stk.pop_back();
                if(stk.size()) stk.pop_back();
                else bkt.push_back(0);
            }
        }
        if(bkt.size() > n - ch.size())return false;
        return true;
    }
    int hubDistance(int N, int sub) {
        n = N;
        memset(dist, -1, sizeof(dist));
        for(int i = 1, mxdist = 0; i < n; ++i) {
            if(getdist(0, i) > mxdist) {
                mxdist = getdist(0, i);
                s = i;
            }
        }
        for(int i = 0, mxdist = 0; i < n; ++i) {
            if(i^s) {
                if(getdist(s, i) > mxdist) {
                    mxdist = getdist(s, i);
                    t = i;
                }
            }
        }
        int hub[2];
        int hubcnt = 0;
        int R = 0x3f3f3f3f;
        for(int i = 0; i < n; ++i) {
            lcadist[i] = (getdist(s, i) + getdist(s, 0) - getdist(i, 0)) / 2;
            if(max(lcadist[i], getdist(s, t) - lcadist[i]) < R) {
                R = max(lcadist[i], getdist(s, t) - lcadist[i]);
                hubcnt = 1;
                hub[0] = i;
            }else if(max(lcadist[i], getdist(s, t) - lcadist[i]) == R && lcadist[i]^lcadist[hub[0]]){
                hubcnt = 2;
                hub[1] = i;
            }
        }
        if(sub <= 2) {
            return R;
        }
        bool balanced = false;
        for(int i = 0; i < hubcnt; ++i) {
            balanced |= solve(hub[i]);
        }
        return (balanced ? 1 : -1) * R;
    }

Compilation message

towns.cpp: In function 'bool solve(int)':
towns.cpp:45:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |         if(ch.size() <= n/2) return true;
      |            ~~~~~~~~~~^~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 384 KB Output is correct
2 Correct 15 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 20 ms 384 KB Output is correct
5 Correct 20 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 384 KB Output is correct
2 Correct 17 ms 384 KB Output is correct
3 Correct 20 ms 384 KB Output is correct
4 Correct 22 ms 384 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 464 KB Output is correct
2 Correct 20 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 20 ms 896 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 384 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 384 KB Output is correct
2 Correct 20 ms 384 KB Output is correct
3 Correct 20 ms 896 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 384 KB Output is correct
2 Correct 20 ms 384 KB Output is correct
3 Correct 20 ms 896 KB Output is correct