Submission #1319273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319273		StefanSebez	전압 (JOI14_voltage)	C++20	0 / 100	46 ms	26460 KiB

voltage

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
const int N=1e5+50,lg=18;
vector<int>E[N];
vector<pair<int,int>>edges;
int n,m;
int par[N][lg+1],depth[N],in[N],out[N],tajm;
bool was[N];
void DFS(int u,int p=0){
    in[u]=++tajm;was[u]=true;
    par[u][0]=p;depth[u]=depth[p]+1;
    for(int i=1;i<=lg;i++)par[u][i]=par[par[u][i-1]][i-1];
    for(auto i:E[u]){
        if(!was[i])DFS(i,u);
        else if(i!=p)edges.pb({i,u});
    }
    out[u]=tajm;
}
int LCA(int u,int v){
    if(depth[u]<depth[v])swap(u,v);
    for(int i=lg;i>=0;i--)if(depth[par[u][i]]>=depth[v])u=par[u][i];if(u==v)return u;
    for(int i=lg;i>=0;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];return par[u][0];
}
int Dist(int u,int v){return depth[u]+depth[v]-2*depth[LCA(u,v)];}
int main(){
    scanf("%i%i",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;scanf("%i%i",&u,&v);
        E[u].pb(v);E[v].pb(u);
    }
    for(int i=1;i<=n;i++)if(!was[i])DFS(i);
    int num=0,U=0,V=0;
    for(auto [u,v]:edges){
        int D=Dist(u,v);
        //printf("%i %i: %i\n",u,v,D);
        if(D%2==0){
            num++;
            if(num==1)U=u,V=v;
            int c1=LCA(u,U),c2=LCA(u,V);
            if(depth[c1]<depth[c2])swap(c1,c2);
            int U1=c1,V1;
            c1=LCA(v,U),c2=LCA(v,V);
            if(depth[c1]<depth[c2])swap(c1,c2);
            V1=c1;
            if(depth[U1]<depth[LCA(u,v)]||depth[V1]<depth[LCA(u,v)])U1=V1=0;
            U=U1,V=V1;
        }
    }
    //for(int i=1;i<=n;i++)printf("%i -> %i\n",i,par[i][0]);
    int res=0;
    if(num==0){

    }
    else if(num==1) res=Dist(U,V)+1;
    else res=Dist(U,V);
    printf("%i\n",res);
    return 0;
}

Compilation message (stderr)

voltage.cpp: In function 'int main()':
voltage.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%i%i",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
voltage.cpp:32:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         int u,v;scanf("%i%i",&u,&v);
      |                 ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 35
• Subtask 4: 0 / 45