답안 #581883

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
581883 2022-06-23T07:40:59 Z 조영욱(#8367) 전압 (JOI14_voltage) C++14
45 / 100
93 ms 17172 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) {
        for(int i=1;i<n;i++) {
            if (find(i)!=find(i+1)) {
                exit(-1);
            }
        }
        int ret=0;
        for(int i=1;i<=n;i++) {
            if (!vis[i]) {
                dfs1(i,0);
                ret--;
            }
        }
        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);
      |         ~~~~~^~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Runtime error 2 ms 3028 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 9252 KB Output is correct
2 Correct 79 ms 13024 KB Output is correct
3 Correct 44 ms 8724 KB Output is correct
4 Correct 73 ms 13120 KB Output is correct
5 Correct 7 ms 3796 KB Output is correct
6 Correct 68 ms 11152 KB Output is correct
7 Correct 72 ms 13292 KB Output is correct
8 Correct 80 ms 16384 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 8892 KB Output is correct
2 Correct 47 ms 16332 KB Output is correct
3 Correct 37 ms 16364 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 52 ms 9200 KB Output is correct
6 Correct 71 ms 8732 KB Output is correct
7 Correct 89 ms 12068 KB Output is correct
8 Correct 93 ms 10080 KB Output is correct
9 Correct 78 ms 12196 KB Output is correct
10 Correct 70 ms 11808 KB Output is correct
11 Correct 62 ms 8276 KB Output is correct
12 Correct 82 ms 10540 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 10752 KB Output is correct
2 Correct 76 ms 17172 KB Output is correct
3 Runtime error 2 ms 3412 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -