제출 #410069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410069		definitelynotmee	도시들 (IOI15_towns)	C++98	25 / 100	18 ms	460 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);

inline bool check(int i, int j, vector<bool>& v, vector<int>& db, int lb, int a){
    if(i==j)
        return 1;
    if(v[i]^v[j])
        return 0;
    if(v[i])
        return 1;
    
    int L = (db[i] + db[j] - getDistance(i,j))>>1;
    return min(L,db[a]-L) >= lb;
}

int hubDistance(int n, int sub){
    int a = 0, b;
    vector<int> ds (n,0), db(n,0);

    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 = ds[b];
    db[0] = ds[b];
    for(int i = 1; i < n; i++){
        if(i==b)
            continue;
        db[i] = getDistance(b,i);
        if(db[i] > maxi)
            maxi = db[i], a = i;
    }
    vector<int> dlca(n,0); // dist(lca(x,0) na arvore enraizada no b, b)
    vector<bool> bsub(n); // verdadeiro se x está na subarvore do b
    int resp = INF;
    for(int i = 0; i < n; i++){
        dlca[i] = (db[0] + db[i] - ds[i])>>1;
        resp = min(resp, max(dlca[i], db[a] - dlca[i]));
    }
    int lb = min(resp, db[a]-resp);
    for(int i = 0; i < n; i++){
        if(dlca[i] < lb)
            bsub[i] = 1;
    }
    // ao parear os indices e considerar apenas aqueles que estão no mesmo grupo,
    // caso haja um majoritário ele será majoritário tanto no vetor inicial quanto no modificado

    stack<int,vector<int>> st;
    vector<int> par(n,-1); // indice do par que o indice i esta pareado, -1 se não estiver
    for(int i = 0; i < (n>>1); i++){
        int cur = 2*i;
        if(!check(cur,cur+1,bsub,db, lb,a))
            continue;
        par[cur] = cur+1;
        par[cur+1] = cur;
        if(st.empty()){
            st.push(cur);
        } else {
            if(check(st.top(), cur, bsub,db,lb,a))
                st.push(cur);
            else st.pop();
        }
    }
    int major = (st.empty() ? n-1 : st.top());
    
    int majorcount = 0;
    for(int i = 0; i < n; i++){
        if(par[i]!=-1){
            if(i&1)
                continue;
            if(check(i,major,bsub,db,lb,a))
                majorcount+=2;
        } else {
            if(check(i,major,bsub,db,lb,a))
                majorcount++;
        }
        
    }
    if(majorcount > (n>>1))
        resp*=-1;

    return resp;
}

컴파일 시 표준 에러 (stderr) 메시지

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:29:28: warning: unused parameter 'sub' [-Wunused-parameter]
   29 | int hubDistance(int n, int sub){
      |                        ~~~~^~~
towns.cpp:39:16: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |     maxi = ds[b];
      |                ^

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