QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#453924#6526. CanvasNGDtuanhWA 3ms51464kbC++174.1kb2024-06-24 14:55:172024-06-24 14:55:17

Judging History

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

  • [2024-06-24 14:55:17]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:51464kb
  • [2024-06-24 14:55:17]
  • 提交

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

void Clear() {
    ans.clear();
    fill(a, a + m + 1, 0);
    For(i, 1, 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, 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) {
    // cout << node << '\n';
    vis[node] = true;
    for (auto [child, id] : adj[node]) {
        if (sccId[child] != sccId[node]) continue;
        if (!vis[child]) DFS(child);
        ans.push_back(id);
        // cout << "push: " << id << '\n';
    }
}

void Topo(int node) {
    // cout << node << '\n';
    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);
        // cout << "push: " << id << '\n';
    }
    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);
    // cout << scc.size() << '\n';

    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 });
        }
    // cout << "\n\n";
    // For(i, 0, (int)scc.size() - 1) cout << sccVis[i] << ' ';
    // cout << '\n';
    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: 0
Wrong Answer
time: 3ms
memory: 51464kb

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 
2
2 1 

result:

wrong answer Participant's solution is incorrect. (test case 2)