| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 581920 |
2022-06-23T08:06:44 Z |
조영욱(#8367) |
전압 (JOI14_voltage) |
C++14 |
|
167 ms |
17592 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 big;
if (abs(one-two)!=1) {
big=1;
}
else {
big=max(one,two);
}
temp[big]++;
if (temp[big]>1) {
pl[big]++;
pl[big+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);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
3156 KB |
Output is correct |
| 6 |
Correct |
3 ms |
3156 KB |
Output is correct |
| 7 |
Correct |
4 ms |
3156 KB |
Output is correct |
| 8 |
Correct |
4 ms |
3156 KB |
Output is correct |
| 9 |
Correct |
3 ms |
3188 KB |
Output is correct |
| 10 |
Correct |
3 ms |
3156 KB |
Output is correct |
| 11 |
Correct |
3 ms |
3196 KB |
Output is correct |
| 12 |
Correct |
3 ms |
3156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
9336 KB |
Output is correct |
| 2 |
Correct |
81 ms |
13424 KB |
Output is correct |
| 3 |
Correct |
47 ms |
9028 KB |
Output is correct |
| 4 |
Correct |
100 ms |
13536 KB |
Output is correct |
| 5 |
Correct |
9 ms |
3924 KB |
Output is correct |
| 6 |
Correct |
101 ms |
11604 KB |
Output is correct |
| 7 |
Correct |
72 ms |
13632 KB |
Output is correct |
| 8 |
Correct |
93 ms |
16772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
9376 KB |
Output is correct |
| 2 |
Correct |
51 ms |
16844 KB |
Output is correct |
| 3 |
Correct |
51 ms |
16840 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3028 KB |
Output is correct |
| 5 |
Correct |
60 ms |
9532 KB |
Output is correct |
| 6 |
Correct |
73 ms |
9084 KB |
Output is correct |
| 7 |
Correct |
96 ms |
12468 KB |
Output is correct |
| 8 |
Correct |
100 ms |
10408 KB |
Output is correct |
| 9 |
Correct |
104 ms |
12536 KB |
Output is correct |
| 10 |
Correct |
95 ms |
12204 KB |
Output is correct |
| 11 |
Correct |
91 ms |
8624 KB |
Output is correct |
| 12 |
Correct |
100 ms |
10916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
11064 KB |
Output is correct |
| 2 |
Correct |
69 ms |
17592 KB |
Output is correct |
| 3 |
Correct |
4 ms |
4692 KB |
Output is correct |
| 4 |
Correct |
86 ms |
10960 KB |
Output is correct |
| 5 |
Correct |
76 ms |
13884 KB |
Output is correct |
| 6 |
Correct |
95 ms |
10340 KB |
Output is correct |
| 7 |
Correct |
167 ms |
14580 KB |
Output is correct |
| 8 |
Correct |
129 ms |
12680 KB |
Output is correct |
| 9 |
Correct |
119 ms |
11576 KB |
Output is correct |
| 10 |
Correct |
152 ms |
15956 KB |
Output is correct |
| 11 |
Correct |
161 ms |
12000 KB |
Output is correct |
| 12 |
Correct |
122 ms |
13640 KB |
Output is correct |
| 13 |
Correct |
99 ms |
10752 KB |
Output is correct |
| 14 |
Correct |
145 ms |
15996 KB |
Output is correct |
| 15 |
Correct |
160 ms |
15896 KB |
Output is correct |
| 16 |
Correct |
139 ms |
14828 KB |
Output is correct |
| 17 |
Correct |
106 ms |
15656 KB |
Output is correct |
| 18 |
Correct |
110 ms |
14508 KB |
Output is correct |
