Submission #1148822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148822		andrejikus	전압 (JOI14_voltage)	C++20	10 / 100	1095 ms	8640 KiB

voltage

#include <bits/stdc++.h>
using namespace std;
int N, M, glob;
vector <int> VG[100096];
int V[100096];
struct EDGE
{
  int u, v;
}E[200096];
inline void DFS(int node)
{
  for(int x : VG[node])
  {
    if(abs(V[x]) == glob) continue;
    V[x] = -V[node];
    DFS(x);
  }
  return;
}
inline bool Check(int index)
{
  bool RET = true;
  glob++;
  EDGE e = E[index];
  remove(VG[e.u].begin(), VG[e.u].end(), e.v);
  VG[e.u].pop_back();
  remove(VG[e.v].begin(), VG[e.v].end(), e.u);
  VG[e.v].pop_back();
  V[e.u] = glob;
  DFS(e.u);
  V[e.v] = glob;
  DFS(e.v);
  for(int i = 1; i <= N; i++) if(abs(V[i]) != glob) {V[i] = glob; DFS(i);}
  for(int i = 1; i <= M; i++) if((i != index) && (V[E[i].u] == V[E[i].v])) {RET = false; break;}
  VG[e.u].push_back(e.v);
  VG[e.v].push_back(e.u);
  return RET;
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> N >> M;
  for(int i = 1; i <= M; i++)
  {
    cin >> E[i].u >> E[i].v;
    VG[E[i].u].push_back(E[i].v);
    VG[E[i].v].push_back(E[i].u);
  }
  int temp = 0;
  for(int i = 1; i <= M; i++) temp += Check(i);
  while(!temp);
  cout << temp << '\n';

  return 0;
}

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