oj.uz

Submission #296374

# Submission time Handle Problem Language Result Execution time Memory
296374 2020-09-10T13:57:41 Z thebes Towns (IOI15_towns) C++14
100 / 100
 29 ms 896 KB 
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
#define F first
#define S second

const int MN = 111;
int N, A, B, C, R, i, j, cnt, rev[MN], pre[MN], suf[MN], dis[2][MN], ds[MN], mat[MN][MN];
map<int,int> mp; vector<pii> vec[MN];
vector<vector<pii>> go; vi ok;
int fnd(int x){return ds[x]=x==ds[x]?x:fnd(ds[x]);}

int chk(int rt){
    go.clear(); memset(mat,-1,sizeof(mat));
    for(auto v : vec[rt]){
        go.push_back(vector<pii>());
        go.back().push_back(v);
    }
    for(i=1;i<=N;i++) ds[i] = i;
    while(go.size()>=2){
        vector<pii> a, b, c;
        a = go[0], b = go[1];
        go.erase(go.begin(),go.begin()+2);
        if(getDistance(a[0].F,b[0].F)==a[0].S+b[0].S){
            mat[fnd(a[0].F)][fnd(b[0].F)]=0;
            mat[fnd(b[0].F)][fnd(a[0].F)]=0;
            int k = min(a.size(),b.size());
            for(int i=k;i<(int)a.size();i++) c.push_back(a[i]);
            for(int i=k;i<(int)b.size();i++) c.push_back(b[i]);
            if(c.size()) go.push_back(c);
        }
        else{
            for(int i=0;i<N;i++) mat[fnd(a[0].F)][i]=max(mat[fnd(a[0].F)][i],mat[fnd(b[0].F)][i]);
            ds[fnd(b[0].F)] = fnd(a[0].F);
            for(auto v : b) a.push_back(v);
            go.push_back(a);
        }
    }
    if(go.empty()) return 0;
    int cand = go[0][0].F, len = go[0][0].S;
    cnt = 0;
    for(auto v : vec[rt]){
        if(fnd(v.F)==fnd(cand)) cnt++;
        else if(mat[fnd(v.F)][fnd(cand)]==-1){
            if(getDistance(v.F,cand)!=len+v.S){
                cnt++;
                for(int i=0;i<N;i++) mat[fnd(cand)][i]=max(mat[fnd(cand)][i],mat[fnd(v.F)][i]);
            }
            else mat[fnd(v.F)][fnd(cand)]=mat[fnd(cand)][fnd(v.F)]=0;
        }
    }
    return cnt;
}

int hubDistance(int _N, int sub) {
    N = _N;
	dis[0][0] = 0;
	A = B = 0; mp.clear(); cnt = 0;
	for(i=1;i<N;i++){
        dis[0][i] = getDistance(A, i);
        if(dis[0][i]>dis[0][B]) B = i;
	}
	dis[1][0] = dis[0][B];
	C = 0;
	for(i=1;i<N;i++){
        if(i==B) continue;
        dis[1][i] = getDistance(B, i);
        int ex = (dis[1][i]+dis[0][i]-dis[0][B])/2;
        mp[dis[1][i]-ex] = 0;
        if(dis[1][i]>dis[1][C]) C = i;
	}
	int D = dis[1][C];
	for(auto it=mp.begin();it!=mp.end();it++){
        it->second = ++cnt;
        rev[cnt] = it->first;
        vec[cnt].clear();
	}
	for(i=1;i<N;i++){
        if(i==B) continue;
        int ex = (dis[1][i]+dis[0][i]-dis[0][B])/2;
        vec[mp[dis[1][i]-ex]].push_back({i, ex});
	}
	R = dis[0][B];
	pre[0] = 1; suf[cnt+1] = 1;
	for(i=1;i<=cnt;i++){
        R = min(R, max(rev[i], D-rev[i]));
        pre[i] = vec[i].size()+pre[i-1];
	}
	for(i=cnt;i>=1;i--) suf[i] = vec[i].size()+suf[i+1];
	ok.clear();
	for(i=1;i<=cnt;i++){
        if(max(rev[i], D-rev[i])==R){
            if(pre[i-1]*2<=N&&suf[i+1]*2<=N)
                ok.push_back(i);
        }
	}
	if(ok.size()==0) return -R;
	else{
        for(auto v : ok){
            if(2*chk(v)<=N) return R;
        }
        return -R;
    }
}

Compilation message

towns.cpp: In function 'int chk(int)':
towns.cpp:30:24: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
   30 |             int k = min(a.size(),b.size());
      |                     ~~~^~~~~~~~~~~~~~~~~~~
towns.cpp:31:21: warning: declaration of 'i' shadows a global declaration [-Wshadow]
   31 |             for(int i=k;i<(int)a.size();i++) c.push_back(a[i]);
      |                     ^
towns.cpp:11:20: note: shadowed declaration is here
   11 | int N, A, B, C, R, i, j, cnt, rev[MN], pre[MN], suf[MN], dis[2][MN], ds[MN], mat[MN][MN];
      |                    ^
towns.cpp:32:21: warning: declaration of 'i' shadows a global declaration [-Wshadow]
   32 |             for(int i=k;i<(int)b.size();i++) c.push_back(b[i]);
      |                     ^
towns.cpp:11:20: note: shadowed declaration is here
   11 | int N, A, B, C, R, i, j, cnt, rev[MN], pre[MN], suf[MN], dis[2][MN], ds[MN], mat[MN][MN];
      |                    ^
towns.cpp:36:21: warning: declaration of 'i' shadows a global declaration [-Wshadow]
   36 |             for(int i=0;i<N;i++) mat[fnd(a[0].F)][i]=max(mat[fnd(a[0].F)][i],mat[fnd(b[0].F)][i]);
      |                     ^
towns.cpp:11:20: note: shadowed declaration is here
   11 | int N, A, B, C, R, i, j, cnt, rev[MN], pre[MN], suf[MN], dis[2][MN], ds[MN], mat[MN][MN];
      |                    ^
towns.cpp:50:25: warning: declaration of 'i' shadows a global declaration [-Wshadow]
   50 |                 for(int i=0;i<N;i++) mat[fnd(cand)][i]=max(mat[fnd(cand)][i],mat[fnd(v.F)][i]);
      |                         ^
towns.cpp:11:20: note: shadowed declaration is here
   11 | int N, A, B, C, R, i, j, cnt, rev[MN], pre[MN], suf[MN], dis[2][MN], ds[MN], mat[MN][MN];
      |                    ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:90:31: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   90 |         pre[i] = vec[i].size()+pre[i-1];
      |                  ~~~~~~~~~~~~~^~~~~~~~~
towns.cpp:92:44: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   92 |  for(i=cnt;i>=1;i--) suf[i] = vec[i].size()+suf[i+1];
      |                               ~~~~~~~~~~~~~^~~~~~~~~
towns.cpp:58:29: warning: unused parameter 'sub' [-Wunused-parameter]
   58 | int hubDistance(int _N, int sub) {
      |                         ~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 384 KB Output is correct
2 Correct 16 ms 896 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 24 ms 896 KB Output is correct
5 Correct 25 ms 896 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 896 KB Output is correct
3 Correct 25 ms 896 KB Output is correct
4 Correct 25 ms 896 KB Output is correct

Subtask #3
13.0 / 13.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 384 KB Output is correct
2 Correct 24 ms 896 KB Output is correct
3 Correct 29 ms 896 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 416 KB Output is correct
2 Correct 27 ms 896 KB Output is correct
3 Correct 24 ms 896 KB Output is correct