# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
16496 |
2015-08-26T14:41:46 Z |
gs14004 |
전압 (JOI14_voltage) |
C++14 |
|
203 ms |
24956 KB |
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> pi;
vector<pi> graph[100005];
vector<pi> odd_cyc, backedg;
int n, m;
int par[100005][17], dep[100005], low[100005], dfn[100005], piv;
bool vis[100005];
bool vise[200005];
int cutedge;
int gap[100005];
void dfs(int x){
low[x] = dfn[x] = ++piv;
for(int i=1; i<=16; i++){
par[x][i] = par[par[x][i-1]][i-1];
}
for(auto &i : graph[x]){
if(!vis[i.second]){
vise[i.first] = 1;
vis[i.second] = 1;
dep[i.second] = dep[x] + 1;
par[i.second][0] = x;
dfs(i.second);
low[x] = min(low[x], low[i.second]);
}
else{
if(vise[i.first]) continue;
vise[i.first] = 1;
low[x] = min(low[x], dfn[i.second]);
if((dep[x] - dep[i.second]) % 2 == 0){
odd_cyc.push_back(pi(i.second, x));
}
else backedg.push_back(pi(i.second, x));
}
}
if(par[x][0] && low[x] == dfn[x]){
cutedge++;
}
}
int lca(int s, int e){
if(dep[s] > dep[e]) swap(s,e);
int dx = dep[e] - dep[s];
for(int i=0; i<17; i++){
if((dx >> i) & 1) e = par[e][i];
}
for(int i=16; i>=0; i--){
if(par[s][i] != par[e][i]){
s = par[s][i];
e = par[e][i];
}
}
if(s != e) return par[s][0];
return s;
}
bool vis2[100005];
int dx[100005];
int cnts;
void fill(int x){
for(auto &i : graph[x]){
if(!vis2[i.second]){
vis2[i.second] = 1;
fill(i.second);
dx[x] += dx[i.second];
}
}
if(par[x][0] && dx[x] == odd_cyc.size()){
cnts++;
}
}
int solve(int x){
cnts = 0;
for(auto &i : odd_cyc){
dx[i.first]++;
dx[i.second]++;
dx[lca(i.first, i.second)]-=2;
}
for(auto &i : backedg){
dx[i.first]--;
dx[i.second]--;
dx[lca(i.first, i.second)]+=2;
}
vis2[x] = 1;
fill(x);
return cnts;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=0; i<m; i++){
int s, e;
scanf("%d %d",&s,&e);
graph[s].push_back(pi(i, e));
graph[e].push_back(pi(i, s));
}
int bad = 0, cnt = 0;
for(int i=1; i<=n; i++){
if(!vis[i]){
vis[i] = 1;
odd_cyc.clear();
backedg.clear();
cutedge = 0;
dfs(i);
if(odd_cyc.empty()){
if(!bad) cnt += cutedge;
}
else{
if(bad){
puts("0");
return 0;
}
bad = 1;
cnt = solve(i) + (odd_cyc.size() == 1);
}
}
}
printf("%d",cnt);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
12544 KB |
Output is correct |
2 |
Correct |
0 ms |
12544 KB |
Output is correct |
3 |
Correct |
0 ms |
12544 KB |
Output is correct |
4 |
Correct |
0 ms |
12544 KB |
Output is correct |
5 |
Correct |
3 ms |
12544 KB |
Output is correct |
6 |
Correct |
2 ms |
12544 KB |
Output is correct |
7 |
Correct |
0 ms |
12544 KB |
Output is correct |
8 |
Correct |
0 ms |
12544 KB |
Output is correct |
9 |
Correct |
0 ms |
12544 KB |
Output is correct |
10 |
Correct |
5 ms |
12544 KB |
Output is correct |
11 |
Correct |
0 ms |
12544 KB |
Output is correct |
12 |
Correct |
0 ms |
12544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
16608 KB |
Output is correct |
2 |
Correct |
64 ms |
19064 KB |
Output is correct |
3 |
Correct |
47 ms |
16608 KB |
Output is correct |
4 |
Correct |
107 ms |
20356 KB |
Output is correct |
5 |
Correct |
7 ms |
13024 KB |
Output is correct |
6 |
Correct |
64 ms |
18004 KB |
Output is correct |
7 |
Correct |
89 ms |
21708 KB |
Output is correct |
8 |
Correct |
80 ms |
21704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
16608 KB |
Output is correct |
2 |
Correct |
38 ms |
21700 KB |
Output is correct |
3 |
Correct |
64 ms |
21704 KB |
Output is correct |
4 |
Correct |
0 ms |
12544 KB |
Output is correct |
5 |
Correct |
64 ms |
18300 KB |
Output is correct |
6 |
Correct |
55 ms |
16240 KB |
Output is correct |
7 |
Correct |
67 ms |
18804 KB |
Output is correct |
8 |
Correct |
86 ms |
19640 KB |
Output is correct |
9 |
Correct |
96 ms |
19876 KB |
Output is correct |
10 |
Correct |
79 ms |
18532 KB |
Output is correct |
11 |
Correct |
78 ms |
16240 KB |
Output is correct |
12 |
Correct |
67 ms |
17452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
19772 KB |
Output is correct |
2 |
Correct |
83 ms |
24956 KB |
Output is correct |
3 |
Correct |
7 ms |
12544 KB |
Output is correct |
4 |
Correct |
74 ms |
19852 KB |
Output is correct |
5 |
Correct |
98 ms |
20872 KB |
Output is correct |
6 |
Correct |
108 ms |
19680 KB |
Output is correct |
7 |
Correct |
149 ms |
22928 KB |
Output is correct |
8 |
Correct |
176 ms |
23280 KB |
Output is correct |
9 |
Correct |
177 ms |
21708 KB |
Output is correct |
10 |
Correct |
104 ms |
24176 KB |
Output is correct |
11 |
Correct |
177 ms |
21820 KB |
Output is correct |
12 |
Correct |
203 ms |
24232 KB |
Output is correct |
13 |
Correct |
146 ms |
21240 KB |
Output is correct |
14 |
Correct |
188 ms |
24524 KB |
Output is correct |
15 |
Correct |
168 ms |
24780 KB |
Output is correct |
16 |
Correct |
179 ms |
23508 KB |
Output is correct |
17 |
Correct |
129 ms |
23460 KB |
Output is correct |
18 |
Correct |
191 ms |
24672 KB |
Output is correct |