oj.uz

Submission #434302

# Submission time Handle Problem Language Result Execution time Memory
434302 2021-06-20T21:58:36 Z benedict0724 Towns (IOI15_towns) C++17
100 / 100
 26 ms 884 KB 
#include "towns.h"
#include <bits/stdc++.h>

using namespace std;

int S = 0, E;
const int INF = 1e9;
int dist[110], dist2[110], distD[110], Hub[110], tmp[110], x[110], y[110];
vector<pair<int, int>> v;

bool getSame(int x, int y)
{
    if(Hub[x] + Hub[y] > getDistance(x, y)) return true;
    return false;
}

int hubDistance(int N, int sub) {
    v.clear();
    for(int i=0;i<N;i++) dist[i] = dist2[i] = Hub[i] = x[i] = y[i] = 0;
	for(int i=1;i<N;i++) dist[i] = getDistance(S, i);
	E = 1;
	for(int i=1;i<N;i++) if(dist[E] < dist[i]) E = i;
	for(int i=1;i<N;i++)
    {
        if(i == E) continue;
        dist2[i] = getDistance(i, E);
    }

    int Rad = dist[E];
    int opt = INF;
    for(int i=1;i<N;i++)
    {
        if(i == E) continue;
        distD[i] = (dist[i] + dist2[i] - Rad)/2;
        x[i] = (dist[i] + Rad - dist2[i])/2;
        y[i] = (-dist[i] + Rad + dist2[i])/2;
    }
    for(int i=1;i<N;i++)
    {
        if(i == E) continue;
        int M = max(x[i], Rad - x[i]);
        for(int j=1;j<N;j++)
        {
            if(j == E) continue;
            tmp[j] = distD[j] + abs(x[i] - x[j]);
            M = max(M, tmp[j]);
        }
        if(M < opt)
        {
            opt = M;
            Hub[S] = x[i];
            Hub[E] = Rad - x[i];
            for(int j=1;j<N;j++)
            {
                if(j == E) continue;
                Hub[j] = tmp[j];
            }
        }
        if(M == opt)
        {
            int cnt1 = 0, cnt2 = 0;
            for(int j=0;j<N;j++)
            {
                if(x[j] < x[i]) cnt1++;
                if(x[j] > x[i]) cnt2++;
            }
            if(cnt1 <= N/2 && cnt2 <= N/2)
            {
                Hub[S] = x[i];
                Hub[E] = Rad - x[i];
                for(int j=1;j<N;j++)
                {
                    if(j == E) continue;
                    Hub[j] = tmp[j];
                }
            }
        }
    }

    int R = 0;
    for(int i=0;i<N;i++) R = max(R, Hub[i]);

    stack<int> st;
    st.push(0);
    int j=1;
    for(int i=1;i<N;i++)
    {
        if(st.empty())
        {
            st.push(i);
            j++;
            continue;
        }
        int t = st.top();
        if(getSame(t, i)) {st.push(i); j++;}
        else
        {
            st.pop();
            v.push_back({i, 1});
            if(st.empty())
            {
                v.push_back({t, j});
                j = 0;
            }
        }
    }
    if(st.empty()) return R;
    int t = st.top();
    int cnt = j;
    for(auto i : v)
    {
        if(getSame(i.first, t)) cnt += i.second;
    }

    if(cnt > N/2) return -R;
    return R;
}

Compilation message

towns.cpp: In function 'bool getSame(int, int)':
towns.cpp:11:25: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   11 | bool getSame(int x, int y)
      |                     ~~~~^
towns.cpp:8:68: note: shadowed declaration is here
    8 | int dist[110], dist2[110], distD[110], Hub[110], tmp[110], x[110], y[110];
      |                                                                    ^
towns.cpp:11:18: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   11 | bool getSame(int x, int y)
      |              ~~~~^
towns.cpp:8:60: note: shadowed declaration is here
    8 | int dist[110], dist2[110], distD[110], Hub[110], tmp[110], x[110], y[110];
      |                                                            ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:17:28: warning: unused parameter 'sub' [-Wunused-parameter]
   17 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 844 KB Output is correct
2 Correct 14 ms 716 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 20 ms 884 KB Output is correct
5 Correct 21 ms 820 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 392 KB Output is correct
2 Correct 14 ms 720 KB Output is correct
3 Correct 19 ms 876 KB Output is correct
4 Correct 19 ms 844 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 716 KB Output is correct
2 Correct 20 ms 840 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 20 ms 832 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 332 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 460 KB Output is correct
2 Correct 19 ms 828 KB Output is correct
3 Correct 19 ms 844 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 396 KB Output is correct
2 Correct 20 ms 840 KB Output is correct
3 Correct 26 ms 860 KB Output is correct