Submission #109201

#TimeUsernameProblemLanguageResultExecution timeMemory
109201njchung99전압 (JOI14_voltage)C++14
100 / 100
227 ms17528 KiB
#include<cstdio> #include<algorithm> #include<vector> #include<cstring> #include<stack> using namespace std; int n, m; stack<int> st; pair<int, int> a[200010]; vector<vector<int>> vt; int par[100010]; int de[100010]; int visited[100010]; int used[200010]; int dp[100010]; int dp1[100010]; int dap = 0; int odd = 0; void dfs(int here) { st.push(here); visited[here] = 1; for (int i = 0; i < vt[here].size(); i++) { int id = vt[here][i]; int next = a[id].first^a[id].second^here; if (!visited[next]) { used[id] = 1; par[next] = here; de[next] = de[here] + 1; dfs(next); } } } int main() { scanf("%d %d", &n, &m); vt.resize(n + 1); for (int i = 0; i < m; i++) { int q, w; scanf("%d %d", &q, &w); vt[q].push_back(i); vt[w].push_back(i); a[i] = { q,w }; } for (int i = 1; i <= n; i++) { if(!visited[i]) dfs(i); } for (int i = 0; i < m; i++) { if (used[i])continue; int x = a[i].first; int y = a[i].second; if (de[x] < de[y]) swap(x, y); if (de[x] % 2 == de[y] % 2) { dp[x]++; dp[y]--; odd++; } else { dp1[x]++; dp1[y]--; } } if (odd == 1)dap++; while (st.size()) { int t = st.top(); int p = par[t]; st.pop(); if (par[t] && dp[t]==odd && dp1[t] == 0)dap++; dp[p] += dp[t]; dp1[p] += dp1[t]; } printf("%d\n", dap); }

Compilation message (stderr)

voltage.cpp: In function 'void dfs(int)':
voltage.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vt[here].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~
voltage.cpp: In function 'int main()':
voltage.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
voltage.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &q, &w);
   ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...