제출 #487269

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
487269		SirCovidThe19th	관광지 (IZhO14_shymbulak)	C++17	100 / 100	225 ms	15872 KiB

shymbulak

#include <bits/stdc++.h>
using namespace std;

#define pil pair<int, long long>
#define f first
#define s second

const int mx = 2e5 + 5;

int n, cycA, cycB, par[mx]; bool vis[mx], inCyc[mx]; pil ans; vector<int> adj[mx];

pil comb(pil A, pil B){ 
    if (A.f > B.f) B = A;
    else if (A.f == B.f) B.s += A.s;
    return B;
}
void getcyc(int u){
    vis[u] = 1; 
    for (int v : adj[u]) if (v != par[u]){ 
        if (vis[v]) tie(cycA, cycB) = {u, v};
        else par[v] = u, getcyc(v);
    }
}
pil dfs(int u, int p){
    pil bst = {0, 1};
    for (int v : adj[u]) if (v != p and !inCyc[v]){
        pil tmp = dfs(v, u); tmp.f++;
        pil pth = {tmp.f + bst.f, bst.s * tmp.s};
        ans = comb(pth, ans);
        bst = comb(tmp, bst);
    }
    return bst;
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i++){
        int a, b; cin >> a >> b; 
        adj[a].push_back(b); adj[b].push_back(a);
    }    
    getcyc(1); vector<int> cyc;
    while (cycB != par[cycA]){
        inCyc[cycB] = 1; cyc.push_back(cycB); 
        cycB = par[cycB];
    }
    vector<pil> store; map<int, long long> window; pil bstL = {0, 0};
    for (int i = 0, l = -(cyc.size() / 2); i < cyc.size(); i++, l++){
        if (l >= 0){
            window[store[l].f - l] -= store[l].s;
            if (!window[store[l].f - l]) window.erase(store[l].f - l);
        }
        pil mxD = dfs(cyc[i], 0); store.push_back(mxD);
        if (window.size()){
            pil bstW = *prev(window.end());
            ans = comb({bstW.f + mxD.f + i, bstW.s * mxD.s}, ans);
        }
        ans = comb({bstL.f + mxD.f - i, bstL.s * mxD.s}, ans);
        if (l >= 0){
            pil mid = store[l]; 
            if (cyc.size() % 2 == 0) mid.s *= 2; //2 paths
            ans = comb({mid.f + mxD.f + (i - l), mid.s * mxD.s}, ans);
        }
        window[mxD.f - i] += mxD.s;
        if (l >= 0) bstL = comb({store[l].f + cyc.size() + l, store[l].s}, bstL);
    }
    cout<<ans.s<<endl;
}

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

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:47:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 0, l = -(cyc.size() / 2); i < cyc.size(); i++, l++){
      |                                            ~~^~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50