| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 581870 |
2022-06-23T07:34:28 Z |
조영욱(#8367) |
전압 (JOI14_voltage) |
C++14 |
|
1000 ms |
9800 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]) {
dfs(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&&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 |
Execution timed out |
1095 ms |
3156 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1086 ms |
8128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
8128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1092 ms |
9800 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
