| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 582014 |
2022-06-23T09:28:47 Z |
박상훈(#8364) |
전압 (JOI14_voltage) |
C++14 |
|
119 ms |
25400 KB |
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int INF = 1e9;
struct Seg{
ll tree[400400], lazy[400400];
void init(int i, int l, int r){
tree[i] = lazy[i] = 0;
if (l==r) return;
int m = (l+r)>>1;
init(i<<1, l, m); init(i<<1|1, m+1, r);
}
void propagate(int i, int l, int r){
tree[i] += (lazy[i]) * (r-l+1);
if (l!=r){
lazy[i<<1] += lazy[i];
lazy[i<<1|1] += lazy[i];
}
lazy[i] = 0;
}
void update(int i, int l, int r, int s, int e, int x){
propagate(i, l, r);
if (r<s || e<l) return;
if (s<=l && r<=e){
lazy[i] += x;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i<<1, l, m, s, e, x); update(i<<1|1, m+1, r, s, e, x);
tree[i] = tree[i<<1] + tree[i<<1|1];
}
ll query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if (r<s || e<l) return 0;
if (s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return query(i<<1, l, m, s, e) + query(i<<1|1, m+1, r, s, e);
}
}tree;
vector<pair<int, int>> adj[100100], G0[100100];
pair<int, int> E[200200];
int n, m, C[200200], col[200200];
bool visited[200200], is_dfs[200200];
namespace HLD{
vector<int> G[100100], root;
int cnt, dep[100100], top[100100], par[100100], in[100100], edge[100100], sz[100100];
void dfs0(int s, int pa = -1){
visited[s] = 1;
for (auto &[v, i]:G0[s]) if (v!=pa){
edge[v] = i;
par[v] = s;
G[s].push_back(v);
dfs0(v, s);
}
}
void dfs1(int s){
sz[s] = 1;
for (auto &v:G[s]){
dfs1(v);
sz[s] += sz[v];
if (sz[v] > sz[G[s][0]]) swap(v, G[s][0]);
}
}
void dfs2(int s){
in[s] = ++cnt;
for (auto &v:G[s]){
if (v==G[s][0]) top[v] = top[s];
else top[v] = v;
dep[v] = dep[s] + 1;
dfs2(v);
}
}
void init(int n){
tree.init(1, 1, n);
fill(visited+1, visited+n+1, 0);
for (int i=1;i<=n;i++) if (!visited[i]){
root.push_back(i);
dfs0(i);
}
for (auto &s:root) dfs1(s);
cnt = 0;
for (auto &s:root){
top[s] = s;
dfs2(s);
}
}
void update(int s, int e, int x){
while(top[s]!=top[e]){
if (dep[top[s]] < dep[top[e]]) swap(s, e);
tree.update(1, 1, n, in[top[s]], in[s], x);
s = par[top[s]];
}
if (s!=e){
if (dep[s] > dep[e]) swap(s, e);
tree.update(1, 1, n, in[s]+1, in[e], x);
}
}
int answer(int t){
int ret = 0;
for (int i=1;i<=n;i++) if (tree.query(1, 1, n, i, i)==t) ret++;
return ret;
}
}
void dfs0(int s, int pa_edge = -1, int c = 0){
visited[s] = 1;
col[s] = c;
for (auto &[v, i]:adj[s]) if (i!=pa_edge){
if (visited[v]) continue;
is_dfs[i] = 1;
G0[s].emplace_back(v, i);
G0[v].emplace_back(s, i);
dfs0(v, i, c^1);
}
}
vector<int> st;
bool dfs1(int s, int e, int pa = -1){
if (s==e) return 1;
for (auto &[v, i]:G0[s]) if (v!=pa){
st.push_back(i);
if (dfs1(v, e, s)) return 1;
st.pop_back();
}
return 0;
}
void sol3(){
for (int i=1;i<=n;i++) if (!visited[i]) dfs0(i);
HLD::init(n);
int odd_cnt = 0;
for (int i=1;i<=m;i++) if (!is_dfs[i]){
int c = 0;
if (col[E[i].first]==col[E[i].second]) c = 1;
if (c==1) HLD::update(E[i].first, E[i].second, 1);
else HLD::update(E[i].first, E[i].second, -INF);
//printf("YES\n");
/*st.clear();
dfs1(E[i].first, E[i].second);
int c = (st.size()&1) ^ 1;
if (c==1) odd_cnt++;
for (auto &j:st){
//printf(" %d %d: %d\n", i, c, j);
if (c==1) C[j]++;
else C[j] = -INF;
}*/
}
/*printf(" %d\n", odd_cnt);
for (int i=1;i<=m;i++) printf("%d ", is_dfs[i]);
printf("\n");
for (int i=1;i<=m;i++) printf("%d ", C[i]);
printf("\n");*/
int ans = (odd_cnt==1);
ans += HLD::answer(odd_cnt);
printf("%d\n", ans);
}
int main(){
scanf("%d %d", &n, &m);
for (int i=1;i<=m;i++){
int x, y;
scanf("%d %d", &x, &y);
adj[x].emplace_back(y, i);
adj[y].emplace_back(x, i);
E[i] = {x, y};
}
//if (n<=1000) naive();
//sol2();
sol3();
return 0;
}
/*bool dfs_col(int s, int c = 0){
visited[s] = c;
for (auto &v:adj[s]){
if (visited[v]<0){
if (!dfs_col(v, c^1)) return 0;
}
else if (visited[v]==c) return 0;
}
return 1;
}
void naive(){
int ans = 0;
for (int i=1;i<=m;i++){
for (int j=1;j<=n;j++) adj[j].clear();
for (int j=1;j<=m;j++) if (i!=j){
adj[E[j].first].push_back(E[j].second);
adj[E[j].second].push_back(E[j].first);
}
fill(visited+1, visited+n+1, -1);
visited[E[i].first] = visited[E[i].second] = 0;
bool flag = 1;
flag &= dfs_col(E[i].first);
flag &= dfs_col(E[i].second);
for (int j=1;j<=n;j++) if (visited[j]<0) flag &= dfs_col(j);
if (flag) ans++;
}
printf("%d\n", ans);
exit(0);
}
vector<int> cyc;
int dfs_cyc(int s, int pa = -1){
visited[s] = 1;
cyc.push_back(s);
int pacnt = 0;
for (auto &v:adj[s]){
if (v==pa){
pacnt++;
if (pacnt==1) continue;
}
if (visited[v]>=0){
return v;
}
int tmp = dfs_cyc(v, s);
if (tmp>=0) return tmp;
}
cyc.pop_back();
return -1;
}
void sol2(){
fill(visited+1, visited+n+1, -1);
int t = dfs_cyc(1), len = -1;
assert(t!=-1);
for (int i=(int)cyc.size()-1;i>=0;i--) if (cyc[i]==t){
len = (int)cyc.size() - i;
break;
}
//for (auto &x:cyc) printf(" %d", x);
//printf(" / %d\n", t);
assert(len!=-1);
if (len%2==0) printf("%d\n", m - len);
else printf("%d\n", len);
}*/
Compilation message
voltage.cpp: In function 'void HLD::dfs0(int, int)':
voltage.cpp:53:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
53 | for (auto &[v, i]:G0[s]) if (v!=pa){
| ^
voltage.cpp: In function 'void dfs0(int, int, int)':
voltage.cpp:118:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
118 | for (auto &[v, i]:adj[s]) if (i!=pa_edge){
| ^
voltage.cpp: In function 'bool dfs1(int, int, int)':
voltage.cpp:131:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
131 | for (auto &[v, i]:G0[s]) if (v!=pa){
| ^
voltage.cpp: In function 'int main()':
voltage.cpp:178:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
178 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
voltage.cpp:181:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
181 | scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
82 ms |
23872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
23940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
119 ms |
25400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
