Submission #1148836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148836		repmann	전압 (JOI14_voltage)	C++20	90 / 100	105 ms	24000 KiB

voltage

#include <bits/stdc++.h>
using namespace std;
int N, M, sol;
bool flag;
struct EDGE
{
  int u, v;
}E[200096];
int V[100096];
bool P[200096];
int DP[100096];
int PARENT[100096];
int UP[20][100096];
int SUM[2][200096];
vector <pair <int, int>> VG[100096];
inline void DFS(int node, vector <int> &I)
{
  DP[node]++;
  for(int i = 1; (1 << i) <= DP[node]; i++) UP[i][node] = UP[i - 1][UP[i - 1][node]];
  for(pair <int, int> p : VG[node])
  {
    if(DP[p.second])
    {
      if(!P[p.first]) I.push_back(p.first);
      P[p.first] = true;
      continue;
    }
    V[p.second] = V[node] ^ 1;
    P[p.first] = true;
    DP[p.second] = DP[node];
    PARENT[p.second] = p.first;
    UP[0][p.second] = node;
    DFS(p.second, I);
  }
  return;
}
inline int LCA(int u, int v)
{
  if(DP[u] > DP[v]) swap(u, v);
  for(int i = 16; i + 1; i--) if(DP[u] < DP[UP[i][v]]) v = UP[i][v];
  if(DP[u] < DP[v]) v = UP[0][v];
  if(u == v) return u;
  for(int i = 16; i + 1; i--) if(UP[i][u] != UP[i][v]) u = UP[i][u], v = UP[i][v];
  return UP[0][u];
}
inline pair <int, int> Pull(int node, vector <int> &I)
{
  V[node] = 2;
  pair <int, int> RET = {0, 0}, temp;
  for(pair <int, int> p : VG[node])
  {
    if(V[p.second] == 2) continue;
    I.push_back(p.first);
    temp = Pull(p.second, I);
    SUM[0][p.first] += temp.first;
    SUM[1][p.first] += temp.second;
    RET.first += SUM[0][p.first];
    RET.second += SUM[1][p.first];
  }
  return RET;
}
inline void Solve(int node)
{
  V[node] = 1;
  vector <int> I;
  DFS(node, I);
  int counter[2] = {0, 0}, temp = 0;
  for(int x : I)
  {
    bool b = V[E[x].u] ^ V[E[x].v];
    counter[b]++;
    SUM[b][PARENT[E[x].u]]++;
    SUM[b][PARENT[E[x].v]]++;
    SUM[b][PARENT[LCA(E[x].u, E[x].v)]] -= 2;
  }
  I.clear();
  if(counter[0] && flag) {cout << "0\n"; exit(0);}
  if(flag) return;
  Pull(node, I);
  for(int x : I) temp += (SUM[0][x] == counter[0]) && (!SUM[1][x]);
  sol += counter[0] == 1;
  sol += temp;
  flag = bool(counter[0]);
  return;
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> N >> M;
  int u, v;
  for(int i = 1; i <= M; i++)
  {
    cin >> u >> v;
    if(u > v) swap(u, v);
    E[i] = {u, v};
    VG[u].push_back({i, v});
    VG[v].push_back({i, u});
  }
  for(int i = 1; i <= N; i++) if(!DP[i]) Solve(i);
  cout << sol << '\n';

  return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45