Submission #54179100

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n)  for(int i=0;i<(n);++i)
#define sizc(x) ((int)x.size())
#define allc(x) x.begin(),x.end()
#define fir first
#define sec second
namespace KnownError_{
    constexpr int N = 2e5+5;
    int n;
    set<pair<int,int>> G[N];
    int del[N];
    int dfn[N],tick;
    int dep[N];
    int st[20][N];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n)  for(int i=0;i<(n);++i)
#define sizc(x) ((int)x.size())
#define allc(x) x.begin(),x.end()
#define fir first
#define sec second
namespace KnownError_{
    constexpr int N = 2e5+5;
    int n;
    set<pair<int,int>> G[N];
    int del[N];
    int dfn[N],tick;
    int dep[N];
    int st[20][N];
    int dmin(int x,int y){return dfn[x]<dfn[y]?x:y;}
    void dfs(int u,int fa){
        st[0][dfn[u]=++tick]=fa;
        for(auto p:G[u]){
            int v=p.fir,w=p.sec;
            if(v==fa)continue;
            dep[v]=dep[u]+w;
            dfs(v,u);
        }
    }
    int lca(int u,int v){
        if(u==v)return u;
        if(dfn[u]>dfn[v])swap(u,v);
        int k=__lg(dfn[v]-dfn[u]);
        return dmin(st[k][dfn[u]+1],st[k][dfn[v]-(1<<k)+1]);
    }
    int dist(int u,int v){return dep[u]+dep[v]-2*dep[lca(u,v)];}
    void main(){
    	cin>>n;
        rep(i,2,n){
            int u,v;
            cin>>u>>v;
            G[u].emplace(v,1);
            G[v].emplace(u,1);
        }
        vector<int> vt;
        rep(i,1,n)if(G[i].size()==2)vt.push_back(i);
        if(vt.size()==n-2){
            cout<<n-1<<'\n';
            return;
        }
        for(auto i:vt){
            del[i]=1;
            auto p1=*G[i].begin(),p2=*G[i].rbegin();
            set<pair<int,int>>().swap(G[i]);
            G[p1.fir].erase({i,p1.sec});
            G[p2.fir].erase({i,p2.sec});
            G[p1.fir].insert({p2.fir,p1.sec+p2.sec});
            G[p2.fir].insert({p1.fir,p1.sec+p2.sec});
        }
        rep(i,1,n)if(!del[i]){dfs(i,0);break;}
        for(int j=1;(1<<j)<=tick;++j)
            rep(i,1,tick-(1<<j)+1)st[j][i]=dmin(st[j-1][i],st[j-1][i+(1<<j-1)]);
        vector<int>().swap(vt);
        int sum=0;
        rep(i,1,n)if(!del[i]&&G[i].size()==1){
            int p=G[i].begin()->fir;
            sum+=G[i].begin()->sec;
            vt.push_back(p);
        }
        sort(allc(vt)),vt.erase(unique(allc(vt)),vt.end());
        int p=vt[0];
        for(auto i:vt)if(dist(vt[0],i)>dist(vt[0],p))p=i;
        int q=vt[0];
        for(auto i:vt)if(dist(p,i)>dist(p,q))q=i;
        int ans=1e9;
        rep(i,1,n)if(!del[i]){
            int now=2*(n-1)-sum;
            if(G[i].size()==1)now+=G[i].begin()->sec;
            now-=max(dist(i,p),dist(i,q));
            ans=min(ans,now);
        }
        cout<<ans<<'\n';
    }
}
signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    KnownError_::main();
}

Submission Info

Compile Error

Main.cpp: In function ‘void KnownError_::main()’:
Main.cpp:49:21: warning: comparison of integer expressions of different signedness: ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
   49 |         if(vt.size()==n-2){
      |            ~~~~~~~~~^~~~~
Main.cpp:64:75: warning: suggest parentheses around ‘-’ inside ‘<<’ [-Wparentheses]
   64 |             rep(i,1,tick-(1<<j)+1)st[j][i]=dmin(st[j-1][i],st[j-1][i+(1<<j-1)]);
      |                                                                          ~^~

Judge Result