QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#219290 | #5663. Tangle: A DAG for storing transactions | JenniferLing# | TL | 27ms | 5888kb | C++17 | 1.2kb | 2023-10-19 11:10:12 | 2023-10-19 11:10:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
vector<int> g[N];
int wei[N], in[N], tot[N];
int par[N][N];
void solve() {
int n, th; cin >> n >> th;
for (int i = 0; i < n; i++) {
int x, y, z, w; cin >> x >> y >> z >> w;
g[x].push_back(y);
g[x].push_back(z);
wei[x] = w;
in[y]++;
in[z]++;
}
queue<int> q;
for (int i = 0; i <= n + 1; ++i) {
if (in[i] == 0) q.push(i);
}
vector<int> res;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
for (int i = 0; i <= n + 1; i++) {
if (par[u][i]) par[v][i] = 1;
par[v][u] = 1;
}
q.push(v);
}
}
for (int i = 0; i <= n + 1; ++i) {
tot[i] = wei[i];
for (int j = 0; j <= n + 1; ++j) {
tot[i] += (par[i][j] ? wei[j] : 0);
}
}
for (int i = 2; i <= n; i++) {
if (tot[i] >= th) {
res.push_back(i);
}
}
int sz = (int)res.size();
for (int x : res) {
cout << x << " " << tot[x] << "\n";
}
cout << sz << "\n";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4084kb
input:
6 12 2 0 1 3 3 0 2 2 4 1 2 1 5 2 3 3 6 3 4 4 7 3 5 5
output:
2 18 3 14 2
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 5888kb
input:
21 20 2 0 1 2 3 1 0 5 4 1 0 2 5 2 1 1 6 1 3 1 7 5 4 1 8 3 7 5 9 2 4 1 10 4 9 1 11 9 4 5 12 4 8 2 13 3 12 2 14 2 10 5 15 11 12 4 16 3 9 2 17 1 16 4 18 0 7 3 19 11 5 2 20 14 4 5 21 19 5 2 22 18 9 4
output:
2 51 3 25 4 50 5 26 7 21 9 35 6
result:
ok 7 lines
Test #3:
score: 0
Accepted
time: 2ms
memory: 4416kb
input:
99 250 2 1 0 1 3 0 2 2 4 3 2 1 5 4 3 4 6 1 2 3 7 5 0 1 8 0 7 2 9 0 8 3 10 3 4 5 11 1 4 4 12 5 6 3 13 12 8 2 14 13 2 3 15 4 10 5 16 5 6 1 17 7 10 1 18 2 5 5 19 9 7 4 20 16 12 5 21 6 3 1 22 7 9 1 23 13 11 1 24 12 9 3 25 7 22 3 26 10 20 5 27 11 12 2 28 26 9 5 29 18 6 5 30 13 17 4 31 25 12 4 32 31 20 3 ...
output:
2 297 3 293 4 290 5 275 6 255 5
result:
ok 6 lines
Test #4:
score: 0
Accepted
time: 2ms
memory: 4416kb
input:
100 200 2 0 1 2 3 2 0 5 4 2 0 2 5 4 0 4 6 2 5 4 7 5 0 5 8 4 2 4 9 2 6 4 10 0 9 3 11 2 8 2 12 4 2 1 13 7 5 3 14 3 4 5 15 10 0 5 16 6 13 1 17 9 10 4 18 12 6 4 19 17 12 1 20 10 8 4 21 2 4 2 22 6 17 2 23 3 12 4 24 21 12 2 25 14 10 5 26 14 21 4 27 13 11 1 28 21 6 1 29 10 5 3 30 26 6 1 31 13 8 5 32 25 19 ...
output:
2 303 3 210 4 296 5 270 6 252 9 225 10 221 12 222 14 201 9
result:
ok 10 lines
Test #5:
score: 0
Accepted
time: 27ms
memory: 4628kb
input:
199 800 2 1 0 1 3 0 2 2 4 3 0 4 5 4 0 3 6 4 3 2 7 0 2 1 8 5 7 3 9 3 0 2 10 1 9 4 11 5 2 4 12 9 4 3 13 7 12 2 14 10 0 1 15 1 6 2 16 5 11 5 17 4 15 4 18 4 14 5 19 11 0 1 20 3 13 5 21 3 4 2 22 20 14 2 23 14 1 5 24 7 19 5 25 13 17 4 26 10 23 5 27 17 12 4 28 12 13 5 29 24 1 4 30 19 7 4 31 18 22 5 32 17 1...
output:
0
result:
ok single line: '0'
Test #6:
score: -100
Time Limit Exceeded
input:
5999 15000 2 0 1 2 3 2 1 1 4 3 1 4 5 1 2 5 6 4 1 1 7 2 6 3 8 4 1 5 9 7 8 2 10 0 4 4 11 3 2 1 12 8 1 1 13 10 3 2 14 1 0 3 15 13 1 3 16 0 4 5 17 6 8 2 18 1 6 1 19 5 2 2 20 4 6 5 21 8 0 2 22 9 20 4 23 17 7 4 24 17 0 1 25 23 3 4 26 12 15 1 27 15 5 3 28 17 25 2 29 17 24 3 30 28 9 2 31 22 6 2 32 12 9 3 33...