QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#453943#6526. CanvasNGDtuanhWA 14ms51764kbC++174.1kb2024-06-24 15:06:032024-06-24 15:06:03

Judging History

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

  • [2024-06-24 15:06:03]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:51764kb
  • [2024-06-24 15:06:03]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define For(i, a, b) for (int i = a; i <= b; ++i)
#define RFor(i, a, b) for (int i = a; i >= b; --i)
#define get_bit(bit, mask) (((mask) >> (bit)) & 1)

const int N = 5e5 + 5;
int INF = 2e18 + 5;
int MOD = 1e9 + 7;

int debug = false;
int cnt;

int sum;
vector<int> ans;

int n, m;
int a[N];
int l[N], x[N], r[N], y[N];
int vis[N];

vector<pair<int, int>> adj[N];

int num[N], low[N], del[N], cur;
int sccId[N];
int sccVis[N];
vector<vector<int>> scc;
int savable[N];
vector<int> sccSavable;
vector<pair<int, int>> sccAdj[N];
stack<int> stk;

void GetInput() {
    cin >> n >> m;
    For(i, 1, m) cin >> l[i] >> x[i] >> r[i] >> y[i];
}

void Rep() {
    ++cnt;
    if (debug) {
        if (cnt == 4) {
            cout << n << ' ' << m << '\n';
            For (i, 1, m) cout << l[i] << ' ' << x[i] << ' ' << r[i] << ' ' << y[i] << '\n';
        }
        return;
    }
    cout << accumulate(a + 1, a + n + 1, 0ll) << '\n';
    for (int e : ans) cout << e << ' ';
    cout << '\n';
}

void Clear() {
    ans.clear();
    fill(a, a + m + 1, 0);
    For(i, 0, n) adj[i].clear();
    fill(vis, vis + n + 1, 0);

    fill(num, num + n + 1, 0);
    fill(low, low + n + 1, 0);
    fill(del, del + n + 1, 0);
    fill(sccVis, sccVis + n + 1, 0);
    fill(sccId, sccId + n + 1, 0);
    fill(savable, savable + n + 1, 0);
    cur = 0;
    scc.clear();
    sccSavable.clear();
    For(i, 0, n) sccAdj[i].clear();
}

void BuildSCC(int node) {
    num[node] = low[node] = ++cur;
    stk.push(node);
    for (auto [child, id] : adj[node]) {
        if (del[child]) continue;
        if (num[child]) low[node] = min(low[node], num[child]);
        else BuildSCC(child), low[node] = min(low[node], low[child]);
    }
    if (num[node] == low[node]) {
        sccId[node] = scc.size();
        scc.emplace_back();
        sccSavable.emplace_back();
        scc.back().push_back(node);
        del[node] = true;
        while (stk.top() != node)
            sccId[stk.top()] = sccId[node],
            scc.back().push_back(stk.top()),
            del[stk.top()] = true,
            stk.pop();
        stk.pop();
    }
}

void DFS(int node) {
    vis[node] = true;
    for (auto [child, id] : adj[node]) {
        if (sccId[child] != sccId[node]) continue;
        if (!vis[child]) DFS(child);
        ans.push_back(id);
    }
}

void Topo(int node) {
    sccVis[node] = true;
    int startPnt = scc[node].front();
    if (sccSavable[node] != 0) startPnt = sccSavable[node];
    for (auto [child, id] : sccAdj[node]) {
        if (!sccVis[child]) Topo(child);
        ans.push_back(id);
    }
    DFS(startPnt);
}

void Solve() {
    Clear();

    For(i, 1, m) 
        if (x[i] == 1 && y[i] == 1)
            ans.push_back(i);

    For(i, 1, m)
        if (x[i] == 1 && y[i] == 2)
            adj[l[i]].push_back({ r[i], i });
        else if (x[i] == 2 && y[i] == 1)
            adj[r[i]].push_back({ l[i], i });

    For(i, 1, n) 
        if (num[i] == 0) 
            BuildSCC(i);

    For(i, 1, m)
        if (x[i] == 2 && y[i] == 2)
            savable[l[i]] = true,
            savable[r[i]] = true;

    For(i, 0, (int)scc.size() - 1)
        for (int node : scc[i]) {
            if (savable[node] == true) sccSavable[i] = node;
            for (auto [child, id] : adj[node])
                if (sccId[node] != sccId[child])
                    sccSavable[sccId[child]] = child,
                    sccAdj[sccId[node]].push_back({ sccId[child], id });
        }

    For(i, 0, (int)scc.size() - 1)
        if (!sccVis[i])
            Topo(i);

    For(i, 1, m)
        if (x[i] == 2 && y[i] == 2)
            ans.push_back(i);

    for (int i : ans)
        a[l[i]] = x[i],
        a[r[i]] = y[i];
}

signed main() {
    #ifndef LOCAL
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif
    int t; cin >> t;
    if (t == 2000) debug = true;
    while (t--) {
        GetInput();
        Solve();
        Rep();
    }
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 48600kb

input:

2
4 4
1 1 2 2
3 2 4 1
1 2 3 2
2 1 4 1
4 2
3 2 4 1
1 2 3 1

output:

7
4 1 2 3 
5
2 1 

result:

ok Correct. (2 test cases)

Test #2:

score: 0
Accepted
time: 3ms
memory: 51432kb

input:

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

output:

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

result:

ok Correct. (1 test case)

Test #3:

score: 0
Accepted
time: 3ms
memory: 51144kb

input:

1
7 5
2 1 6 2
1 2 6 1
1 1 5 1
2 2 7 1
1 1 7 2

output:

8
3 2 1 4 5 

result:

ok Correct. (1 test case)

Test #4:

score: 0
Accepted
time: 7ms
memory: 51288kb

input:

1
7 6
2 1 7 2
2 1 4 2
1 2 4 1
2 1 6 1
1 1 6 2
2 2 6 1

output:

9
4 1 3 2 6 5 

result:

ok Correct. (1 test case)

Test #5:

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

input:

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

output:

7
3 4 1 5 2 

result:

ok Correct. (1 test case)

Test #6:

score: 0
Accepted
time: 8ms
memory: 51140kb

input:

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

output:

8
1 5 3 4 2 6 

result:

ok Correct. (1 test case)

Test #7:

score: -100
Wrong Answer
time: 14ms
memory: 51764kb

input:

2000
15 16
2 2 3 1
12 2 15 1
3 2 9 1
6 2 14 1
2 1 15 2
5 2 6 1
7 1 10 1
9 2 15 1
2 2 3 1
4 2 12 1
2 2 9 1
5 2 8 2
3 2 13 1
12 1 13 2
9 2 13 1
5 1 14 2
15 15
5 2 11 1
1 2 8 1
8 1 15 2
6 2 8 2
8 2 9 1
1 1 6 2
6 1 9 2
2 2 5 1
2 1 10 2
7 2 10 1
1 1 15 2
5 2 15 1
7 1 11 2
1 1 2 1
5 2 9 1
15 14
3 1 5 2
1 ...

output:

15 14
7 2 12 1
5 2 14 2
3 2 8 1
1 2 13 1
2 1 12 2
1 1 10 2
1 1 3 1
3 1 13 2
5 2 8 1
1 2 14 1
2 2 7 1
3 2 10 1
5 2 10 1
5 1 14 2

result:

wrong answer 4 is not in the permutation. (test case 1)