제출 #1320088

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1320088		StefanSebez	전압 (JOI14_voltage)	C++20	100 / 100	223 ms	7472 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;
int n,m;
vector<pair<int,int>>edges;
struct DSU{
    int par[N],sajz[N],bip;bool f[N];
    vector<array<int,3>>undo;
    DSU(){Init();}
    void Init(){for(int i=1;i<N;i++)par[i]=i,sajz[i]=1,f[i]=0;bip=0;}
    pair<int,bool>FS(int u){
        if(u==par[u])return {u,false};
        auto [v,x]=FS(par[u]);
        return {v,x^f[u]};
    }
    bool US(int u,int v){
        auto [u1,c1]=FS(u);
        auto [u2,c2]=FS(v);
        if(u1==u2){
            int x=0;
            if(c1==c2)x=1;
            bip+=x;
            undo.pb({u1,u2,x});
            return false;
        }
        if(sajz[u1]>sajz[u2])swap(u1,u2),swap(c1,c2);
        par[u1]=u2;
        sajz[u2]+=sajz[u1];
        f[u1]=c1^c2^1;
        undo.pb({u1,u2,0});
        return true;
    }
    void Undo(){
        auto [u1,u2,x]=undo.back();undo.pop_back();
        if(u1==u2)bip-=x;
        else{
            par[u1]=u1;
            sajz[u2]-=sajz[u1];
            f[u1]=0;
        }
    }
}dsu;
int Solve(int l,int r){
    if(l>r)return 0;
    int mid=l+r>>1;
    for(int i=l;i<mid;i++)dsu.US(edges[i].fi,edges[i].se);
    for(int i=mid+1;i<=r;i++)dsu.US(edges[i].fi,edges[i].se);
    int res=0;
    if(dsu.bip==0){
        auto [u,v]=edges[mid];
        auto [u1,c1]=dsu.FS(u);
        auto [u2,c2]=dsu.FS(v);
        if(u1!=u2||c1==c2)res++;//,printf("[%i %i]\n",edges[mid].fi,edges[mid].se);
    }
    for(int i=mid+1;i<=r;i++)dsu.Undo();
    dsu.US(edges[mid].fi,edges[mid].se);
    res+=Solve(mid+1,r);
    for(int i=l;i<=mid;i++)dsu.Undo();
    for(int i=mid;i<=r;i++)dsu.US(edges[i].fi,edges[i].se);
    res+=Solve(l,mid-1);
    for(int i=mid;i<=r;i++)dsu.Undo();
    return res;
}
int main(){
    scanf("%i%i",&n,&m);
    for(int i=0;i<m;i++){
        int u,v;scanf("%i%i",&u,&v);
        edges.pb({u,v});
    }
    int res=Solve(0,m-1);
    printf("%i\n",res);
    return 0;
}

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

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

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