| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 581909 |
2022-06-23T07:58:55 Z |
조영욱(#8367) |
전압 (JOI14_voltage) |
C++14 |
|
199 ms |
17516 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=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: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 |
3 ms |
3028 KB |
Output is correct |
| 5 |
Correct |
3 ms |
3120 KB |
Output is correct |
| 6 |
Correct |
3 ms |
3156 KB |
Output is correct |
| 7 |
Correct |
3 ms |
3156 KB |
Output is correct |
| 8 |
Incorrect |
3 ms |
3156 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
9436 KB |
Output is correct |
| 2 |
Correct |
76 ms |
13600 KB |
Output is correct |
| 3 |
Correct |
48 ms |
9208 KB |
Output is correct |
| 4 |
Correct |
116 ms |
13500 KB |
Output is correct |
| 5 |
Correct |
7 ms |
3924 KB |
Output is correct |
| 6 |
Correct |
107 ms |
11556 KB |
Output is correct |
| 7 |
Correct |
95 ms |
13768 KB |
Output is correct |
| 8 |
Correct |
116 ms |
16864 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
9380 KB |
Output is correct |
| 2 |
Correct |
41 ms |
16824 KB |
Output is correct |
| 3 |
Correct |
49 ms |
16720 KB |
Output is correct |
| 4 |
Correct |
3 ms |
3028 KB |
Output is correct |
| 5 |
Correct |
49 ms |
9488 KB |
Output is correct |
| 6 |
Correct |
89 ms |
9008 KB |
Output is correct |
| 7 |
Correct |
120 ms |
12460 KB |
Output is correct |
| 8 |
Correct |
75 ms |
10372 KB |
Output is correct |
| 9 |
Correct |
100 ms |
12516 KB |
Output is correct |
| 10 |
Correct |
96 ms |
12208 KB |
Output is correct |
| 11 |
Correct |
73 ms |
8640 KB |
Output is correct |
| 12 |
Correct |
94 ms |
10976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
11088 KB |
Output is correct |
| 2 |
Correct |
67 ms |
17516 KB |
Output is correct |
| 3 |
Correct |
4 ms |
4692 KB |
Output is correct |
| 4 |
Correct |
123 ms |
10980 KB |
Output is correct |
| 5 |
Correct |
97 ms |
13892 KB |
Output is correct |
| 6 |
Correct |
102 ms |
10660 KB |
Output is correct |
| 7 |
Correct |
156 ms |
14540 KB |
Output is correct |
| 8 |
Correct |
192 ms |
12716 KB |
Output is correct |
| 9 |
Correct |
136 ms |
11652 KB |
Output is correct |
| 10 |
Correct |
191 ms |
16100 KB |
Output is correct |
| 11 |
Correct |
199 ms |
11948 KB |
Output is correct |
| 12 |
Correct |
161 ms |
13752 KB |
Output is correct |
| 13 |
Incorrect |
118 ms |
11884 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
