QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#304719 | #6526. Canvas | ucup-team2894# | WA | 6ms | 49104kb | C++17 | 4.2kb | 2024-01-14 01:14:11 | 2024-01-14 01:14:12 |
Judging History
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)