Submission #2471501
Source Code Expand
#include <bits/stdc++.h> using namespace std; const int N = 100005; int n, m, val[N], c[N]; vector <int> g[N], newG[N]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; ++i) cin >> c[i]; cin >> m; while(m--) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } for (int i = 1; i <= n; ++i) { sort(g[i].begin(), g[i].end(), [&](int x, int y) { return c[x] < c[y]; }); if (g[i].size() == 0) continue; int last = 0; for (int j = 1; j < g[i].size(); ++j) { int x = g[i][j]; if (c[x] > c[g[i][j - 1]]) last = g[i][j - 1]; if (last) { newG[x].push_back(last); // c[x] > c[last] (x -> last) } } for (int &j : g[i]) { if (c[i] > c[j]) newG[i].push_back(j); // i -> j } } vector < pair<int,int> > vec; for (int i = 1; i <= n; ++i) vec.push_back(make_pair(c[i], i)); sort(vec.begin(), vec.end()); for (int i = 0; i < vec.size(); ++i) { int u = vec[i].second; int mx = 0; for (int &v : newG[u]) { mx = max(mx, val[v]); } val[u] = mx + 1; } // calc sum long long sum = 0; for (int i = 1; i <= n; ++i) { sum += val[i]; } printf("%lld\n", sum); }
Submission Info
Submission Time | |
---|---|
Task | J - Black Company |
User | cheater2k |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1246 Byte |
Status | WA |
Exec Time | 115 ms |
Memory | 14712 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 100 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04, 10_rand_00, 10_rand_01, 10_rand_02, 10_rand_03, 10_rand_04, 11_max_rand_00, 11_max_rand_01, 11_max_rand_02, 11_max_rand_03, 11_max_rand_04, 20_path_00, 20_path_01, 20_path_02, 20_path_03, 20_path_04, 21_max_path_00, 21_max_path_01, 21_max_path_02, 21_max_path_03, 21_max_path_04, 30_star_00, 30_star_01, 30_star_02, 30_star_03, 30_star_04, 31_max_star_00, 31_max_star_01, 31_max_star_02, 31_max_star_03, 31_max_star_04, 40_clique_00, 40_clique_01, 40_clique_02, 40_clique_03, 40_clique_04, 41_max_clique_00, 41_max_clique_01, 41_max_clique_02, 41_max_clique_03, 41_max_clique_04, 50_discon_00, 50_discon_01, 50_discon_02, 50_discon_03, 50_discon_04, 51_max_discon_00, 51_max_discon_01, 51_max_discon_02, 51_max_discon_03, 51_max_discon_04, 60_noedge_00, 60_noedge_01, 60_noedge_02, 60_noedge_03, 60_noedge_04, 61_max_noedge_00, 61_min_noedge |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_00 | AC | 3 ms | 4992 KB |
00_sample_01 | AC | 3 ms | 4992 KB |
00_sample_02 | AC | 3 ms | 4992 KB |
00_sample_03 | AC | 3 ms | 4992 KB |
00_sample_04 | AC | 3 ms | 4992 KB |
10_rand_00 | AC | 38 ms | 8448 KB |
10_rand_01 | AC | 100 ms | 13436 KB |
10_rand_02 | AC | 50 ms | 10484 KB |
10_rand_03 | AC | 21 ms | 7164 KB |
10_rand_04 | AC | 16 ms | 6524 KB |
11_max_rand_00 | AC | 44 ms | 9968 KB |
11_max_rand_01 | AC | 115 ms | 14712 KB |
11_max_rand_02 | AC | 22 ms | 7160 KB |
11_max_rand_03 | AC | 48 ms | 10356 KB |
11_max_rand_04 | WA | 83 ms | 12792 KB |
20_path_00 | AC | 3 ms | 4992 KB |
20_path_01 | AC | 46 ms | 10744 KB |
20_path_02 | AC | 15 ms | 6528 KB |
20_path_03 | AC | 23 ms | 7548 KB |
20_path_04 | WA | 25 ms | 7808 KB |
21_max_path_00 | AC | 65 ms | 12920 KB |
21_max_path_01 | AC | 65 ms | 12920 KB |
21_max_path_02 | AC | 67 ms | 12276 KB |
21_max_path_03 | WA | 67 ms | 12276 KB |
21_max_path_04 | WA | 66 ms | 12280 KB |
30_star_00 | AC | 34 ms | 9720 KB |
30_star_01 | AC | 41 ms | 11640 KB |
30_star_02 | AC | 45 ms | 11512 KB |
30_star_03 | AC | 6 ms | 5504 KB |
30_star_04 | AC | 54 ms | 12536 KB |
31_max_star_00 | AC | 62 ms | 13300 KB |
31_max_star_01 | AC | 57 ms | 13684 KB |
31_max_star_02 | AC | 70 ms | 13812 KB |
31_max_star_03 | AC | 76 ms | 13812 KB |
31_max_star_04 | AC | 63 ms | 13812 KB |
40_clique_00 | AC | 29 ms | 9344 KB |
40_clique_01 | AC | 5 ms | 5248 KB |
40_clique_02 | AC | 4 ms | 4992 KB |
40_clique_03 | AC | 47 ms | 10752 KB |
40_clique_04 | AC | 3 ms | 4992 KB |
41_max_clique_00 | AC | 43 ms | 11520 KB |
41_max_clique_01 | AC | 42 ms | 11520 KB |
41_max_clique_02 | AC | 55 ms | 11520 KB |
41_max_clique_03 | AC | 53 ms | 11520 KB |
41_max_clique_04 | AC | 52 ms | 11392 KB |
50_discon_00 | AC | 6 ms | 5504 KB |
50_discon_01 | AC | 41 ms | 8832 KB |
50_discon_02 | AC | 63 ms | 11128 KB |
50_discon_03 | AC | 36 ms | 8188 KB |
50_discon_04 | AC | 58 ms | 10488 KB |
51_max_discon_00 | AC | 59 ms | 11380 KB |
51_max_discon_01 | AC | 47 ms | 11892 KB |
51_max_discon_02 | AC | 74 ms | 12532 KB |
51_max_discon_03 | AC | 50 ms | 9716 KB |
51_max_discon_04 | WA | 74 ms | 12276 KB |
60_noedge_00 | AC | 5 ms | 5248 KB |
60_noedge_01 | AC | 13 ms | 6008 KB |
60_noedge_02 | AC | 9 ms | 5756 KB |
60_noedge_03 | AC | 19 ms | 6520 KB |
60_noedge_04 | AC | 12 ms | 6008 KB |
61_max_noedge_00 | AC | 20 ms | 6644 KB |
61_min_noedge | AC | 3 ms | 4992 KB |