답안 #581914

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
581914 2022-06-23T08:03:36 Z 조영욱(#8367) 전압 (JOI14_voltage) C++14
45 / 100
204 ms 17504 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;
int root[100001];

void dfs(int v,int prev){
    par[v]=prev;
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        root[nt]=root[v];
        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));
        assert(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) {
            root[i]=i;
            dfs(i,0);
        }
    }
    for(int i=1;i<=n;i++) {
        adj[i].clear();
    }
    bool flag=false;
    int d=0;
    int pr=-1;
    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) {
                if (root[edge[i].first]!=pr) {
                    printf("0");
                }
                continue;
            }
            pr=root[edge[i].first];
            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=0;i<m;i++) {
        if (!vis[edge[i].first]) {
            continue;
        }
        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:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
voltage.cpp: In function 'void dfs1(int, int)':
voltage.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
voltage.cpp: In function 'void dfs2(int, int)':
voltage.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
voltage.cpp: In function 'int main()':
voltage.cpp:150:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |             for(int j=0;j<temp.size();j++) {
      |                         ~^~~~~~~~~~~~
voltage.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
voltage.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 3 ms 3192 KB Output is correct
6 Correct 3 ms 3156 KB Output is correct
7 Correct 2 ms 3156 KB Output is correct
8 Incorrect 2 ms 3156 KB Output isn't correct
9 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 9332 KB Output is correct
2 Correct 107 ms 13504 KB Output is correct
3 Correct 53 ms 9128 KB Output is correct
4 Correct 97 ms 13500 KB Output is correct
5 Correct 9 ms 3808 KB Output is correct
6 Correct 103 ms 11528 KB Output is correct
7 Correct 94 ms 13644 KB Output is correct
8 Correct 114 ms 16724 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 9404 KB Output is correct
2 Correct 42 ms 16804 KB Output is correct
3 Correct 53 ms 16828 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 70 ms 9556 KB Output is correct
6 Correct 72 ms 9120 KB Output is correct
7 Correct 93 ms 12512 KB Output is correct
8 Correct 114 ms 10348 KB Output is correct
9 Correct 94 ms 12568 KB Output is correct
10 Correct 102 ms 12112 KB Output is correct
11 Correct 91 ms 8660 KB Output is correct
12 Correct 107 ms 10916 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 10976 KB Output is correct
2 Correct 86 ms 17504 KB Output is correct
3 Correct 4 ms 4692 KB Output is correct
4 Correct 77 ms 10900 KB Output is correct
5 Correct 86 ms 13732 KB Output is correct
6 Correct 119 ms 10440 KB Output is correct
7 Correct 127 ms 14432 KB Output is correct
8 Correct 135 ms 12660 KB Output is correct
9 Correct 142 ms 11580 KB Output is correct
10 Correct 204 ms 15972 KB Output is correct
11 Correct 143 ms 11936 KB Output is correct
12 Correct 196 ms 13624 KB Output is correct
13 Incorrect 107 ms 10772 KB Output isn't correct
14 Halted 0 ms 0 KB -