| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 581987 |
2022-06-23T09:14:14 Z |
박상훈(#8364) |
전압 (JOI14_voltage) |
C++14 |
|
1000 ms |
22496 KB |
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int INF = 1e9;
vector<pair<int, int>> adj[100100], G0[100100];
pair<int, int> E[200200];
int n, m, C[200200];
bool visited[200200], is_dfs[200200];
void dfs0(int s, int pa_edge = -1){
visited[s] = 1;
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);
}
}
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);
int odd_cnt = 0;
for (int i=1;i<=m;i++) if (!is_dfs[i]){
//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);
for (int i=1;i<=m;i++) if (C[i]==odd_cnt && is_dfs[i]) ans++;
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 dfs0(int, int)':
voltage.cpp:13:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
13 | for (auto &[v, i]:adj[s]) if (i!=pa_edge){
| ^
voltage.cpp: In function 'bool dfs1(int, int, int)':
voltage.cpp:26:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
26 | for (auto &[v, i]:G0[s]) if (v!=pa){
| ^
voltage.cpp: In function 'int main()':
voltage.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
voltage.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5204 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5076 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5076 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5204 KB |
Output is correct |
| 7 |
Correct |
9 ms |
5212 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5076 KB |
Output is correct |
| 9 |
Correct |
5 ms |
5076 KB |
Output is correct |
| 10 |
Correct |
11 ms |
5204 KB |
Output is correct |
| 11 |
Correct |
9 ms |
5204 KB |
Output is correct |
| 12 |
Correct |
10 ms |
5152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
13776 KB |
Output is correct |
| 2 |
Correct |
102 ms |
17544 KB |
Output is correct |
| 3 |
Correct |
50 ms |
13760 KB |
Output is correct |
| 4 |
Correct |
108 ms |
19560 KB |
Output is correct |
| 5 |
Correct |
12 ms |
6228 KB |
Output is correct |
| 6 |
Correct |
90 ms |
16956 KB |
Output is correct |
| 7 |
Correct |
88 ms |
22496 KB |
Output is correct |
| 8 |
Correct |
95 ms |
22472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
13760 KB |
Output is correct |
| 2 |
Correct |
49 ms |
21544 KB |
Output is correct |
| 3 |
Correct |
47 ms |
21644 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
175 ms |
16636 KB |
Output is correct |
| 6 |
Correct |
88 ms |
13380 KB |
Output is correct |
| 7 |
Correct |
328 ms |
18128 KB |
Output is correct |
| 8 |
Correct |
334 ms |
19572 KB |
Output is correct |
| 9 |
Correct |
223 ms |
19460 KB |
Output is correct |
| 10 |
Correct |
226 ms |
17520 KB |
Output is correct |
| 11 |
Correct |
164 ms |
13772 KB |
Output is correct |
| 12 |
Correct |
208 ms |
15904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1090 ms |
15436 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
