QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#219290#5663. Tangle: A DAG for storing transactionsJenniferLing#TL 27ms5888kbC++171.2kb2023-10-19 11:10:122023-10-19 11:10:12

Judging History

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

  • [2023-10-19 11:10:12]
  • 评测
  • 测评结果:TL
  • 用时:27ms
  • 内存:5888kb
  • [2023-10-19 11:10:12]
  • 提交

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...

output:


result: