QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#114879 | #6526. Canvas | xaphoenix | WA | 13ms | 77288kb | C++14 | 4.4kb | 2023-06-23 20:43:36 | 2023-06-23 20:43:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define LC k<<1
#define RC k<<1|1
#define IO cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define rep(i,a,n) for (int i = a; i < n; i++)
#define repn(i,a,n) for (int i = a; i <= n; i++)
#define per(i,a,n) for (int i = (n) - 1; i >= a; i--)
#define pern(i,a,n) for (int i = n; i >= a; i--)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;
typedef pair<double, double> PDD;
typedef pair<ull, ull> PUU;
typedef pair<LL, LL> PLL;
const int N = 510000;
const int M = 1100000;
const int mod = 1e9+7;
const int inf = (int)1e9;
const LL INF = 1e18;
const double eps = 1e-9;
mt19937_64 Rand((unsigned long long)new char);
#define rand Rand
int T, n, m, a[N];
struct inst {
int id, l, r, x, y;
void read(int d) {
id = d;
cin >> l >> x >> r >> y;
}
}b[N];
int st1[N], st2[N];
vector<int> f[N], h[N];
vector<PII> g[N];
int t1, t2, pp[N], cp[N], qp[N], du[N], fp[N];
queue<int> que;
int dfn[N], low[N], instack[N], scc[N], cnt, scc_cnt;
stack<int> st;
vector<int> sc[N];
void tarjan(int x) {
dfn[x] = low[x] = ++cnt;
st.push(x);
instack[x] = 1;
for (auto p: g[x]) {
int y = p.fi;
if (dfn[y]==0) {
tarjan(y);
low[x] = min(low[x], low[y]);
}
else if (instack[y]) low[x] = min(low[x], dfn[y]);
}
if (low[x]==dfn[x]) {
++scc_cnt;
while (!st.empty() && st.top() != x) {
scc[st.top()] = scc_cnt;
instack[st.top()] = 0;
st.pop();
}
st.pop();
scc[x] = scc_cnt;
instack[x] = 0;
}
}
vector<int> ans;
void dfs(int x) {
fp[x] = 1;
for (auto p: g[x]) {
int y = p.fi, id = p.se;
if (scc[y] == scc[x]);
else st2[++t2] = id;
}
for (auto p: g[x]) {
int y = p.fi, id = p.se;
if (scc[y] == scc[x]) {
if (fp[y]) st1[++t1] = id;
else st2[++t2] = id, dfs(y);
}
}
}
int main() {
IO;
cin >> T;
while (T--) {
cin >> n >> m;
cnt = scc_cnt = 0;
repn(i, 1, n) a[i] = pp[i] = dfn[i] = qp[i] = du[i] = fp[i] = 0, f[i].clear(), g[i].clear(), sc[i].clear(), h[i].clear();
repn(i, 1, m) cp[i] = 0;
t1 = t2 = 0;
while (!que.empty()) que.pop();
repn(i, 1, m) {
b[i].read(i);
if (b[i].x == 2 && b[i].y == 2) {
cp[b[i].id] = 1;
st2[++t2] = i;
if (!pp[b[i].l]) pp[b[i].l] = 1, que.push(b[i].l);
if (!pp[b[i].r]) pp[b[i].r] = 1, que.push(b[i].r);
}
else if (b[i].x == 1 && b[i].y == 1) {
cp[b[i].id] = 1;
st1[++t1] = i;
}
else {
f[b[i].l].pb(i), f[b[i].r].pb(i);
}
}
while (!que.empty()) {
int now = que.front(); que.pop();
for (auto x: f[now]) {
auto p = b[x];
if (cp[p.id]) continue;
cp[p.id] = 1;
if (p.l == now) {
if (p.x == 1) {
st2[++t2] = p.id;
if (!pp[p.r]) pp[p.r] = 1, que.push(p.r);
}
else st1[++t1] = p.id;
}
else {
if (p.y == 1) {
st2[++t2] = p.id;
if (!pp[p.l]) pp[p.l] = 1, que.push(p.l);
}
else st1[++t1] = p.id;
}
}
}
repn(i, 1, m) {
if (!cp[b[i].id]) {
if (b[i].x == 1) g[b[i].l].pb(mp(b[i].r, i));
else g[b[i].r].pb(mp(b[i].l, i));
}
}
repn(i, 1, n) if (dfn[i] == 0) tarjan(i);
repn(i, 1, n) sc[scc[i]].pb(i);
repn(i, 1, m) {
if (!cp[b[i].id]) {
int x, y;
if (b[i].x == 1) x = b[i].l, y = b[i].r;
else x = b[i].r, y = b[i].l;
if (scc[x] == scc[y]);
else {
du[y] += 1;
h[scc[x]].pb(scc[y]);
qp[y] = 1;
}
}
}
repn(i, 1, scc_cnt) {
if (du[i] == 0) que.push(i);
}
ans.clear();
while (!que.empty()) {
int now = que.front(); que.pop();
int st = sc[now][0];
for (auto x: sc[now]) if (qp[x]) {
st = x;
break;
}
dfs(st);
for (auto y: h[now]) {
du[y]--;
if (du[y] == 0) que.push(y);
}
}
repn(i, 1, t1) ans.pb(st1[i]);
while (t2) ans.pb(st2[t2]), t2--;
for (auto p: ans) a[b[p].l] = b[p].x, a[b[p].r] = b[p].y;
int res = 0;
repn(i, 1, n) res += a[i];
cout << res << "\n";
rep(i, 0, ans.size()) {
cout << ans[i];
assert(ans[i] <= m);
if (i != ans.size() - 1) cout << " ";
else cout << "\n";
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 76820kb
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: 7ms
memory: 75968kb
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 5 4 3 2 1 7 6 11 10 9 12
result:
ok Correct. (1 test case)
Test #3:
score: 0
Accepted
time: 6ms
memory: 77288kb
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: 75984kb
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 3 2 1 6 5
result:
ok Correct. (1 test case)
Test #5:
score: 0
Accepted
time: 9ms
memory: 75232kb
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 1 3 5 4 2
result:
ok Correct. (1 test case)
Test #6:
score: 0
Accepted
time: 9ms
memory: 76120kb
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 4 1 5 6 3 2
result:
ok Correct. (1 test case)
Test #7:
score: -100
Wrong Answer
time: 13ms
memory: 76448kb
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 6 1 9 3 11 8 15 13 14 10 2 5 4 16 12 20 14 6 5 1 13 10 9 8 12 11 15 3 2 7 4 21 2 14 8 11 6 10 13 3 9 12 4 7 1 5 18 7 9 13 4 3 11 1 5 8 12 6 10 14 2 21 6 5 2 7 1 3 18 12 11 14 10 13 9 19 16 17 8 4 15 21 3 11 9 2 6 13 14 8 5 7 4 12 10 1 21 3 7 15 11 8 1 5 14 2 9 6 13 4 12 10 19 11 7 9 16 13 15 17...
result:
wrong answer Integer parameter [name=p_i] equals to 21, violates the range [1, 14] (test case 13)