QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#453899#6526. CanvasNGDtuanhWA 11ms52012kbC++173.8kb2024-06-24 14:36:162024-06-24 14:36:17

Judging History

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

  • [2024-06-24 14:36:17]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:52012kb
  • [2024-06-24 14:36:16]
  • 提交

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 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() {
    cout << accumulate(a + 1, a + n + 1, 0ll) << '\n';
    for (int e : ans) cout << e << ' ';
    cout << '\n';
}

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

    fill(num + 1, num + n + 1, 0);
    fill(low + 1, low + n + 1, 0);
    fill(del + 1, del + n + 1, 0);
    fill(sccVis + 1, sccVis + n + 1, 0);
    fill(sccId + 1, sccId + n + 1, 0);
    fill(savable + 1, savable + n + 1, 0);
    cur = 0;
    scc.clear();
    sccSavable.clear();
    For(i, 1, 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;
    while (t--) {
        GetInput();
        Solve();
        Rep();
    }
}

详细

Test #1:

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

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: 51720kb

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: 51228kb

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: 0ms
memory: 52012kb

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: 50988kb

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: 3ms
memory: 50276kb

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: 11ms
memory: 50300kb

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:

23
7 10 1 9 13 3 11 15 14 2 8 5 6 4 16 12 
13
14 12 11 3 15 6 2 5 7 4 
21
2 6 10 3 11 13 9 12 7 8 4 1 14 5 
13
7 11 1 5 3 9 2 
19
6 3 2 7 11 14 10 13 16 19 1 18 12 9 15 
14
3 10 11 7 12 2 6 1 
18
3 15 6 7 11 9 13 4 12 2 14 10 
17
11 16 1 4 17 6 13 12 8 15 9 3 14 2 5 18 
16
9 8 11 3 14 1 4 5 6 19 12 ...

result:

wrong answer Integer parameter [name=p_i] equals to 21, violates the range [1, 15] (test case 2)