Submission #581886

# Submission time Handle Problem Language Result Execution time Memory
581886 2022-06-23T07:43:06 Z 조영욱(#8367) 전압 (JOI14_voltage) C++14
0 / 100
70 ms 33160 KB
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> P;
vector<P> edge;
vector<int> adj[100001];
int n,m;
int p[100001];

int find(int a) {
    return p[a]<0?a:p[a]=find(p[a]);
}

void merge(int a,int b) {
    a=find(a);
    b=find(b);
    if (a==b){
        return;
    }
    p[b]=a;
}

int dep[100001];
int par[100001];
vector<int> vec;

void dfs(int v,int prev){
    par[v]=prev;
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (nt!=prev) {
            dep[nt]=dep[v]+1;
            dfs(nt,v);
        }
    }
}

int ind[100001];
int mn[100001];
bool vis[100001];
int f=1;

void dfs1(int v,int prev) {
    vis[v]=true;
    ind[v]=f++;
    mn[v]=ind[v];
int cnt=0;
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (vis[nt]) {
        if (nt==prev) {
            cnt++;
        }
if (nt!=prev||cnt>1)
            mn[v]=min(mn[v],ind[nt]);
continue;
        }
        dfs1(nt,v);
        mn[v]=min(mn[v],mn[nt]);
    }
}

int value[100001];

void dfs2(int v,int type) {
    vis[v]=true;
    value[v]=type;
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (!vis[nt])
            dfs2(nt,-type);
    }
}

int pl[100002];
int temp[100002];

int main(void){
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        edge.push_back(P(u,v));
    }
    memset(p,-1,sizeof(p));
    for(int i=0;i<m;i++) {
        if (find(edge[i].first)!=find(edge[i].second)) {
            adj[edge[i].first].push_back(edge[i].second);
            adj[edge[i].second].push_back(edge[i].first);
            merge(edge[i].first,edge[i].second);
        }
    }
    for(int i=1;i<=n;i++) {
        if (dep[i]==0) {
            dfs(i,0);
        }
    }
    for(int i=1;i<=n;i++) {
        adj[i].clear();
    }
    bool flag=false;
    int d=0;
    for(int i=0;i<m;i++) {
        adj[edge[i].first].push_back(edge[i].second);
        adj[edge[i].second].push_back(edge[i].first);
        if (dep[edge[i].first]%2==dep[edge[i].second]%2) {
            if (flag) {
                continue;
            }
            flag=true;
            int lca=-1;
            int a=edge[i].first;
            int b=edge[i].second;
            if (dep[a]<dep[b]) {
                swap(a,b);
            }
            while (dep[a]>dep[b]) {
                a=par[a];
                d++;
            }
            while (a!=b) {
                a=par[a];
                b=par[b];
                d+=2;
            }
            d++;
            lca=a;
            P save=edge[i];
            while (edge[i].first!=lca) {
                vec.push_back(edge[i].first);
                edge[i].first=par[edge[i].first];
            }
            vec.push_back(lca);
            vector<int> temp;
            while (edge[i].second!=lca) {
                temp.push_back(edge[i].second);
                edge[i].second=par[edge[i].second];
            }
            edge[i]=save;
            reverse(temp.begin(),temp.end());
            for(int j=0;j<temp.size();j++) {
                vec.push_back(temp[j]);
            }
        }
    }
    if (!flag) {
        int ret=0;
        for(int i=1;i<=n;i++) {
            if (!vis[i]) {
                dfs1(i,0);
                ret--;
            }
            assert(ind[i]==mn[i]);
        }
        for(int i=1;i<=n;i++) {
            if (ind[i]==mn[i]) {
                ret++;
            }
        }
        printf("%d",ret);
        return 0;
    }
    for(int i=0;i<d;i++) {
        vis[vec[i]]=true;
    }
    for(int i=0;i<d;i++) {
        dfs2(vec[i],i+1);
    }
    for(int i=1;i<=n;i++){
        if (!vis[i]) {
            dfs2(i,d+1);
        }
        //printf("%d ",value[i]);
    }
    for(int i=0;i<m;i++) {
        if (value[edge[i].first]==value[edge[i].second]) {
            printf("0");
            return 0;
        }
        int one=value[edge[i].first];
        int two=value[edge[i].second];
        if (one>0&&two>0&&one<=d&&two<=d&&vec[one-1]==edge[i].first&&vec[two-1]==edge[i].second&&(one+1==two||two+1==one||two-one==d-1||one-two==d-1)) {
            int small;
            if (abs(one-two)!=1) {
                small=d;
            }
            else {
                small=min(one,two);
            }
            temp[small]++;
            if (temp[small]>1) {
                pl[small]++;
                pl[small+1]--;
            }
            continue;
        }
        if (one+two==0) {
            continue;
        }
        if (one<0&&two>0) {
            swap(one,two);
        }
        if (1LL*one*two>0) {
            one=abs(one);
            two=abs(two);
            bool flag=false;
            if (two>one&&(two-one)%2==1) {
                flag=true;
            }
            if (two<one&&(two-one)%2==0) {
                flag=true;
            }
            if (flag) {
                swap(one,two);
            }
            if (one<two) {
                pl[1]++;
                pl[one+1]--;
                pl[two+1]++;
                pl[d+1]--;
            }
            else {
                pl[two+1]++;
                pl[one+1]--;
            }
        }
        else {
            one=abs(one);
            two=abs(two);
            one=abs(one);
            two=abs(two);
            bool flag=false;
            if (two>one&&(two-one)%2==1) {
                flag=true;
            }
            if (two<one&&(two-one)%2==0) {
                flag=true;
            }
            if (!flag) {
                swap(one,two);
            }
            if (one<two) {
                pl[1]++;
                pl[one+1]--;
                pl[two+1]++;
                pl[d+1]--;
            }
            else {
                pl[two+1]++;
                pl[one+1]--;
            }
        }
    }
    int ret=0;
    int val=0;
    for(int i=1;i<=d;i++) {
        val+=pl[i];
        if (val==0) {
            ret++;
        }
    }
    printf("%d",ret);
}

Compilation message

voltage.cpp: In function 'void dfs(int, int)':
voltage.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
voltage.cpp: In function 'void dfs1(int, int)':
voltage.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
voltage.cpp: In function 'void dfs2(int, int)':
voltage.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
voltage.cpp: In function 'int main()':
voltage.cpp:141:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |             for(int j=0;j<temp.size();j++) {
      |                         ~^~~~~~~~~~~~
voltage.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
voltage.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 6228 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 18104 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 32 ms 8912 KB Output is correct
2 Correct 42 ms 16432 KB Output is correct
3 Runtime error 55 ms 33160 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 70 ms 21428 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -