QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#644233#9449. New School Termarayi_chris_max#RE 1ms5644kbC++203.4kb2024-10-16 11:57:392024-10-16 11:57:42

Judging History

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

  • [2024-10-16 11:57:42]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:5644kb
  • [2024-10-16 11:57:39]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define fr first
#define sc second
using namespace std;

const int N = 5005;
const int M = 1e6 + 2;
const ll mod = 998244353LL;

int n, m;
pair<int, int> fp[M];
struct nd {
    bool odd;
    int par;
    int num_odd, num_ev;
};

nd pr[2 * N];
int d[2 * N];
int sum;
int gp(int x) {
    if (pr[x].par != x) {
        int rt = gp(pr[x].par);
        pr[x].odd ^= pr[pr[x].par].odd;
        pr[x].par = rt;
        // pr[x].num_odd = pr[x].num_ev = 0;
    }
    return pr[x].par;
}

bool check() {
    if (sum == n) return true;
    bitset<N> sm;
    sm[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (d[i] == 0) continue;
        int x = d[i];
        while (x) {
            sm |= (sm << (i * ((x + 1) >> 1)));
            x >>= 1;
        }
        if (sm[n - sum]) return true;
    }
    return sm[n - sum];
}

int dp[2 * N];
bool ans[2 * N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> fp[i].fr >> fp[i].sc;
    }
    reverse(fp, fp + m);
    for (int i = 1; i <= 2 * n; i++) {
        pr[i] = {0, i, 0, 1};
        d[1]++;
    }
    for (int i = 0; i < m; i++) {
        int a = fp[i].fr;
        int b = fp[i].sc;
        int rt_a = gp(a);
        int rt_b = gp(b);
        if (rt_a == rt_b) continue;

        int nda = pr[rt_a].num_odd, nea = pr[rt_a].num_ev;
        d[abs(nda - nea)]--;
        sum -= min(nda, nea);
        int ndb = pr[rt_b].num_odd, neb = pr[rt_b].num_ev;
        d[abs(ndb - neb)]--;
        sum -= min(ndb, neb);

        bool fl = pr[a].odd ^ pr[b].odd ^ 1;
        if (fl) {
            nda += neb;
            nea += ndb;

        } else {
            nda += ndb;
            nea += neb;
        }

        d[abs(nda - nea)]++;
        sum += min(nda, nea);

        if (check()) {
            pr[rt_b].par = rt_a;
            pr[rt_b].odd = fl;
            if (fl) {
                pr[rt_a].num_odd += pr[rt_b].num_ev;
                pr[rt_a].num_ev += pr[rt_b].num_odd;

            } else {
                pr[rt_a].num_odd += pr[rt_b].num_odd;
                pr[rt_a].num_ev += pr[rt_b].num_ev;
            }
        } else {
            d[abs(nda - nea)]--;
            sum -= min(nda, nea);

            fl ^= 1;
            pr[rt_b].par = rt_a;
            pr[rt_b].odd = fl;
            if (fl) {
                pr[rt_a].num_odd += pr[rt_b].num_ev;
                pr[rt_a].num_ev += pr[rt_b].num_odd;

            } else {
                pr[rt_a].num_odd += pr[rt_b].num_odd;
                pr[rt_a].num_ev += pr[rt_b].num_ev;
            }

            d[abs(pr[rt_a].num_ev - pr[rt_a].num_odd)]++;
            sum += min(pr[rt_a].num_ev, pr[rt_a].num_odd);
        }
    }

    dp[0] = 1;
    int ss = n - sum;
    for (int i = 1; i <= 2 * n; i++) {
        if (gp(i) != i) continue;
        int d = abs(pr[i].num_ev - pr[i].odd);
        for (int x = ss; x >= 0; x--) {
            if (dp[x] && !dp[min(ss, x + d)]) dp[min(ss, x + d)] = i;
        }
    }

    int sm;
    while (ss != 0) {
        sm = dp[ss];
        assert(sm != 0);
        ans[sm] = 1;
        int d = abs(pr[sm].num_ev - pr[sm].odd);
        ss -= d;
    }

    for (int i = 1; i <= 2 * n; i++) {
        cout << (ans[gp(i)] ^ pr[i].odd);
    }
    cout << endl;
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3652kb

input:

2 4
1 3
2 4
1 4
1 2

output:

0101

result:

ok Output is valid. OK

Test #2:

score: 0
Accepted
time: 1ms
memory: 5644kb

input:

3 7
2 5
1 3
4 6
2 6
4 5
2 4
5 6

output:

001101

result:

ok Output is valid. OK

Test #3:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

1 0

output:

10

result:

ok Output is valid. OK

Test #4:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

1 1
1 2

output:

01

result:

ok Output is valid. OK

Test #5:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

2 3
2 4
3 4
1 2

output:

0110

result:

ok Output is valid. OK

Test #6:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

3 8
4 6
3 5
1 4
2 4
1 6
1 2
3 4
4 5

output:

010101

result:

ok Output is valid. OK

Test #7:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

4 9
4 7
3 8
1 5
2 7
2 8
6 8
7 8
1 4
1 6

output:

01010110

result:

ok Output is valid. OK

Test #8:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

5 16
3 6
9 10
2 7
1 10
1 5
2 10
3 5
5 6
3 4
2 5
4 5
3 8
4 7
6 8
1 6
7 10

output:

1101000101

result:

ok Output is valid. OK

Test #9:

score: -100
Runtime Error

input:

6 13
4 5
2 9
3 8
4 8
4 11
10 12
3 4
3 9
5 11
2 8
5 10
5 8
1 11

output:


result: