Submission #409478

#	Time	Username	Problem	Language	Result	Execution time	Memory
409478		definitelynotmee	도시들 (IOI15_towns)	C++98	0 / 100	17 ms	844 KiB

towns

#include <bits/stdc++.h>
#include "towns.h"
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const int MAXN = 0;

int getDistance(int i, int j);

int hubDistance(int n, int sub){
    vector<int> ds (n,0), db(n,0), da(n,-1);
    int a, b;
    int maxi = -1;
    for(int i = 1; i < n; i++){
        ds[i] = getDistance(0,i);
        if(ds[i] > maxi)
            maxi = ds[i], b = i;
    }
    maxi = -1;
    for(int i = 0; i < n; i++){
        if(i==b)
            continue;
        db[i] = getDistance(b,i);
        if(ds[i] > maxi)
            maxi = ds[i], a = i;
    }
    da[a] = 0;
    da[b] = db[a];
    vector<int> dlca(n,0), v(n);
    for(int i = 0; i < n; i++){
        dlca[i] = db[0] + db[i] - ds[i];
    }
    iota(v.begin(),v.end(),0);
    sort(v.begin(),v.end(),[&](int x, int y){
        return dlca[x] < dlca[y];
    });
    vector<int> type(n,0);
    /*
        1- subarvore do b
        2- filho de h2

    */
    int lastid = 0;

    int resp = -1;

    for(int i = 1; i < n; i++){
        if(dlca[v[i-1]] == dlca[v[i]]){
            type[v[i]] = type[v[i-1]];
            continue;
        }
        int cur = v[i];
        if(da[cur] != -1)
            da[cur] = getDistance(cur,a);
        if(da[cur] <= db[cur]){
            int r1 = (da[cur] + db[cur] - db[a])>>1;

            if(da[cur] == db[cur]){
                resp = max(da[cur]-r1, db[cur]-r1);
            } else {
                int r2 = (da[v[i-1]] + db[v[i-1]] - db[a])>>1;
                resp = max(db[a] - da[cur] + r1, db[a] - db[v[i-1]] + r2);
            }
            break;
        } else {
            type[cur] = 1;
        }
        lastid = i;
    }
    return resp;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:50:9: warning: variable 'lastid' set but not used [-Wunused-but-set-variable]
   50 |     int lastid = 0;
      |         ^~~~~~
towns.cpp:17:28: warning: unused parameter 'sub' [-Wunused-parameter]
   17 | int hubDistance(int n, int sub){
      |                        ~~~~^~~
towns.cpp:35:9: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |     da[b] = db[a];
      |         ^
towns.cpp:34:9: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   34 |     da[a] = 0;
      |         ^

• Subtask 1: 0 / 13
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39