QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#304719#6526. Canvasucup-team2894#WA 6ms49104kbC++174.2kb2024-01-14 01:14:112024-01-14 01:14:12

Judging History

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

  • [2024-01-14 01:14:12]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:49104kb
  • [2024-01-14 01:14:11]
  • 提交

answer

#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(a) (a).begin(), (a).end()
#define unique(a) a.resize(unique(a.begin(), a.end()) - a.begin())

using namespace std;

#ifdef ONPC
mt19937 rnd(223);
#else
mt19937 rnd(chrono::high_resolution_clock::now()
			.time_since_epoch().count());
#endif

#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

using ll = long long;
using ld = double;

const int maxn = 5e5 + 100, inf = 1e9 + 100;

namespace myscc {

    bool vis[maxn];
    vector<int> eo[maxn];
    vector<int> e[maxn];
    vector<int> ord;

    void dfs(int v) {
        vis[v] = 1;
        for (int i : e[v])
            if (!vis[i])
                dfs(i);
        ord.push_back(v);
    }

    int col[maxn];

    void go(int v, int cs) {
        col[v] = cs;
        vis[v] = 1;
        for (int i : eo[v])
            if (!vis[i])
                go(i, cs);
    }

    vector<vector<int>> get_scc(int n, vector<pair<int, int>> ed) {
        ord.clear();
        fill(vis, vis + n, 0);
        for (int i = 0; i < n; i++) {
            e[i].clear();
            eo[i].clear();
        }
        for (auto [v, u] : ed) {
            e[v].push_back(u);
            eo[u].push_back(v);
        }
        for (int i = 0; i < n; i++)
            if (!vis[i])
                dfs(i);
        reverse(all(ord));
        fill(vis, vis + n, 0);
        int cs = 0;
        for (int v : ord)
            if (!vis[v]) {
                go(v, cs);
                cs++;
            }
        vector<int> bad(cs);
        for (auto [v, u] : ed)
            if (col[v] != col[u])
                bad[col[u]] = 1;
        vector<vector<int>> who(cs);
        for (int i = 0; i < n; i++)
            who[col[i]].push_back(i);
        vector<vector<int>> ans;
        for (int i = 0; i < cs; i++)
            if (!bad[i])
                ans.push_back(who[i]);
        return ans;
    }

}
using myscc::get_scc;

vector<pair<int, int>> graph[500005];
int l[500005], r[500005], x[500005], y[500005];
vector<int> ord;
bool vis[500005];

void dfs(int n) {
    vis[n] = 1;
    for (auto e : graph[n]) {
        if (!vis[e.first]) {
            dfs(e.first);
        }
        ord.push_back(e.second);
    }
}

void solve() {
    int T;
    cin >> T;
    while(T--) {
        int N, M;
        cin >> N >> M;
        vector<int> mark(N + 5);
        ord.clear();
        for (int i= 1; i <= N; i++) {
            graph[i].clear();
            vis[i] = 0;
        }
        vector<pair<int, int>> edge_list;
        for (int i= 1; i <= M; i++) {
            cin >> l[i] >> x[i] >> r[i] >> y[i];
            if (x[i] > y[i]) {
                swap(l[i], r[i]);
                swap(x[i], y[i]);
            }
            if (x[i] == 2 && y[i] == 2) {
                mark[l[i]] = mark[r[i]] = 1;
            }
            else if (x[i] == 1 && y[i] == 2) {
                graph[l[i]].emplace_back(r[i], i);
                edge_list.emplace_back(l[i], r[i]);
            }
            else {
                ord.push_back(i);
            }
        }
        auto root = get_scc(N, edge_list);
        for (auto v : root) {
            for (int n : v) {
                n++;
                if (!vis[n] && mark[n]) {
                    dfs(n);
                    break;
                }
            }
            if (!vis[v[0]+1]) {
                dfs(v[0]+1);
            }
        }
        for (int i = 1; i <= M; i++) {
            if (x[i] == 2 && y[i] == 2) {
                ord.push_back(i);
            }
        }
        vector<int> val(N + 5);
        for (int i : ord) {
            val[l[i]] = x[i];
            val[r[i]] = y[i];
        }
        int sum = 0;
        for (int v : val) {
            sum += v;
        }
        cout << sum << "\n";
        for (int i : ord) {
            cout << i << " ";
        }
        cout << "\n";
    }
}

int main() {
#ifdef ONPC
    freopen("../a.in", "r", stdin);
//    freopen("../a.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;
    cout.precision(20);
    solve();
    cerr << "\n\nConsumed " << TIME << endl;
}

詳細信息

Test #1:

score: 100
Accepted
time: 6ms
memory: 47820kb

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

result:

ok Correct. (2 test cases)

Test #2:

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

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 8 10 5 7 6 11 9 1 3 4 2 12 

result:

ok Correct. (1 test case)

Test #3:

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

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: 4ms
memory: 48968kb

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 2 6 5 3 

result:

ok Correct. (1 test case)

Test #5:

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

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
4 1 3 5 2 

result:

ok Correct. (1 test case)

Test #6:

score: -100
Wrong Answer
time: 4ms
memory: 47780kb

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:

3
5 1 

result:

wrong output format Unexpected end of file - int32 expected (test case 1)