QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#480655#996. 割点mfeitveer#WA 5ms16456kbC++141.8kb2024-07-16 17:09:522024-07-16 17:09:53

Judging History

你现在查看的是最新测评结果

  • [2024-07-16 17:09:53]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:16456kb
  • [2024-07-16 17:09:52]
  • 提交

answer

/*
  ! 以渺小启程,以伟大结束。
  ! Created: 2024/07/16 16:52:12
*/
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
// #define int long long
#define mp(x, y) make_pair(x, y)
#define eb(...) emplace_back(__VA_ARGS__)
#define fro(i, x, y) for (int i = (x); i <= (y); i++)
#define pre(i, x, y) for (int i = (x); i >= (y); i--)
inline void JYFILE19();

typedef long long i64;
typedef pair<int, int> PII;

bool ST;
const int N = 1e6 + 10;
const int mod = 998244353;

int n, m, ct, u[N], v[N], head[N];
int dn[N], lw[N], vs[N];
struct edge {
  int to, nxt, val;
} e[N << 1];

inline void add(int x, int y, int z) {
  e[++ct] = {y, head[x], z}, head[x] = ct;
  e[++ct] = {x, head[y], z}, head[y] = ct;
}
inline void dfs(int x, int f) {
  dn[x] = lw[x] = ++ct; int son = 0;
  for (int i = head[x]; i; i = e[i].nxt) {
    if (e[i].to == f) continue;
    if (!dn[e[i].to]) {
      son++;
      dfs(e[i].to, x);
      lw[x] = min(lw[x], lw[e[i].to]);
      if (x != 1 && lw[e[i].to] >= dn[x]) vs[x] = 1;
    } else {
      lw[x] = min(lw[x], dn[e[i].to]);
      if (x != 1 && lw[e[i].to] >= dn[x]) vs[x] = 1;
    }
  }
  if (x == 1 && son >= 2) vs[x] = 1;
}

signed main() {
  JYFILE19();
  cin >> n >> m;
  fro(i, 1, m) {
    cin >> u[i] >> v[i];
    add(u[i], v[i], i);
  }
  ct = 0;
  fro(i, 1, n)
    if (dn[i] == 0) dfs(i, 0);
  ct = 0;
  fro(i, 1, n)
    if (vs[i] == 1) ct++;
  cout << ct << "\n";
  fro(i, 1, n)
    if (vs[i] == 1) cout << i << " ";
  cout << "\n";
  return 0;
}

bool ED;
inline void JYFILE19() {
  // freopen("", "r", stdin);
  // freopen("", "w", stdout);
  srand(random_device{}());
  ios::sync_with_stdio(0), cin.tie(0);
  double MIB = fabs((&ED-&ST)/1048576.), LIM = 512;
  cerr << "MEMORY: " << MIB << endl, assert(MIB<=LIM);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 5ms
memory: 16456kb

input:

12783 21968
4933 7832
8238 2739
3628 7841
9169 6390
7850 8797
8120 8710
5306 9807
10166 2063
2666 5157
5015 4651
4790 12586
10366 7137
12440 7218
6330 3670
2735 8492
1968 2750
6237 1112
6578 9221
743 3820
7155 4583
2537 9747
11331 9916
4454 5631
2978 10340
5293 1803
4944 4296
11800 2742
7903 2018
10...

output:

3099
10 13 22 26 27 29 31 32 33 34 35 37 39 44 45 47 49 50 53 55 56 61 62 63 66 67 78 84 91 94 99 105 106 110 118 121 126 127 132 133 138 144 145 146 151 155 156 163 166 168 174 176 177 178 179 181 183 186 187 188 192 194 196 199 200 202 205 208 210 212 214 215 219 220 223 225 226 234 239 244 247 24...

result:

wrong answer 1st numbers differ - expected: '1440', found: '3099'