QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#484073 | #4892. 序列 | Hunster | 10 | 75ms | 124832kb | C++14 | 4.5kb | 2024-07-19 15:49:20 | 2024-07-19 15:49:21 |
Judging History
answer
#include <bits/stdc++.h>
constexpr int inf32 = (int)(1e9) + 9;
constexpr int N = 100005;
constexpr int M = 2000006;
int n, m, tot;
struct Cond { int u[3], w; };
Cond cond[N];
std::vector<int> graph[M];
std::vector<int> hash[N], id[N][4];
int h(int i, int x) { return std::lower_bound(hash[i].begin(), hash[i].end(), x) - hash[i].begin(); }
bool in_sta[M];
int dfn[M], low[M], bel[M], scc, dfc;
std::stack<int> sta;
void tarjan(int u) {
sta.push(u);
in_sta[u] = 1;
low[u] = dfn[u] = ++dfc;
for (int v : graph[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = std::min(low[u], low[v]);
}
else if (in_sta[v]) {
low[u] = std::min(low[u], dfn[v]);
}
}
if (low[u] >= dfn[u]) {
int x;
scc++;
do {
x = sta.top();
sta.pop();
in_sta[x] = 0;
bel[x] = scc;
}
while (x != u);
}
}
int deg[M], tpn[M];
std::vector<int> _graph[M];
int main() {
std::cin.sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n >> m;
for (int i = 1; i <= m; i++) {
std::cin >> cond[i].u[0] >> cond[i].u[1] >> cond[i].u[2] >> cond[i].w;
hash[cond[i].u[0]].push_back(cond[i].w);
hash[cond[i].u[1]].push_back(cond[i].w);
hash[cond[i].u[2]].push_back(cond[i].w);
}
for (int i = 1; i <= n; i++) {
std::sort(hash[i].begin(), hash[i].end());
hash[i].resize(std::unique(hash[i].begin(), hash[i].end()) - hash[i].begin());
for (int o = 0; o < 4; o++) {
id[i][o].resize(hash[i].size());
for (int j = 0; j < hash[i].size(); j++) id[i][o][j] = ++tot;
}
for (int j = 1; j < hash[i].size(); j++) {
graph[id[i][0][j - 1]].push_back(id[i][0][j]);
graph[id[i][1][j - 1]].push_back(id[i][1][j]);
graph[id[i][2][j]].push_back(id[i][2][j - 1]);
graph[id[i][3][j]].push_back(id[i][3][j - 1]);
graph[id[i][1][j - 1]].push_back(id[i][0][j]);
graph[id[i][2][j]].push_back(id[i][3][j - 1]);
}
}
for (int i = 1; i <= m; i++)
for (int x : {0, 1, 2}) for (int y : {0, 1, 2}) {
if (x == y) continue;
int u = cond[i].u[x], v = cond[i].u[y], w = cond[i].w;
int wu = h(u, w), wv = h(v, w);
graph[id[u][0][wu]].push_back(id[v][2][wv]);
graph[id[u][3][wu]].push_back(id[v][1][wv]);
}
// std::cerr << tot << std::endl;
for (int i = 1; i <= tot; i++) if (!dfn[i]) tarjan(i);
// std::cerr << "0:\n";
// for (int i = 1; i <= n; i++) for (int j = 0; j < hash[i].size(); j++) std::cerr << bel[id[i][0][j]] << " \n"[j + 1 == hash[i].size()];
// std::cerr << "1:\n";
// for (int i = 1; i <= n; i++) for (int j = 0; j < hash[i].size(); j++) std::cerr << bel[id[i][1][j]] << " \n"[j + 1 == hash[i].size()];
// std::cerr << "2:\n";
// for (int i = 1; i <= n; i++) for (int j = 0; j < hash[i].size(); j++) std::cerr << bel[id[i][2][j]] << " \n"[j + 1 == hash[i].size()];
// std::cerr << "3:\n";
// for (int i = 1; i <= n; i++) for (int j = 0; j < hash[i].size(); j++) std::cerr << bel[id[i][3][j]] << " \n"[j + 1 == hash[i].size()];
// std::cerr << std::endl;
bool flag = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < hash[i].size(); j++) {
flag &= bel[id[i][0][j]] != bel[id[i][2][j]];
flag &= bel[id[i][1][j]] != bel[id[i][3][j]];
}
}
if (!flag) puts("NO");
else {
for (int i = 1; i <= tot; i++) for (int j : graph[i]) if (bel[i] != bel[j]) {
_graph[bel[i]].push_back(bel[j]);
deg[bel[j]]++;
}
std::queue<int> que;
for (int i = 1; i <= scc; i++) if (!deg[i]) que.push(i);
int cnt = 0;
while (que.size()) {
int u = que.front();
que.pop();
tpn[u] = ++cnt;
for (int v : _graph[u])
if (--deg[v] == 0)
que.push(v);
}
puts("YES");
for (int i = 1; i <= n; i++) {
int ans = inf32;
for (int j = 0; j < hash[i].size(); j++) {
if (tpn[bel[id[i][1][j]]] > tpn[bel[id[i][3][j]]]) {
ans = hash[i][j];
break;
}
}
printf("%d%c", ans, " \n"[i == n]);
}
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 20
Accepted
time: 16ms
memory: 112444kb
input:
10 10 6 3 10 133562624 8 7 6 685486592 4 2 7 332482851 10 8 9 211550017 2 10 1 165556251 10 8 5 211550017 6 8 2 332482851 4 9 2 332482851 8 1 4 193658790 9 6 10 728674154
output:
YES 165556251 332482851 133562624 193658790 211550017 728674154 685486592 211550017 728674154 133562624
result:
ok solution is correct
Test #2:
score: -20
Wrong Answer
time: 11ms
memory: 112156kb
input:
10 9 5 3 7 489042696 10 9 3 489042696 5 9 4 589265757 1 3 7 489042696 9 3 10 489042696 2 8 7 402617168 2 4 5 564742148 1 8 3 615037121 2 8 4 564742148
output:
YES 615037121 402617168 489042696 564742148 589265757 1000000009 402617168 615037121 589265757 489042696
result:
wrong answer Integer 1000000009 violates the range [1, 10^9]
Subtask #2:
score: 10
Accepted
Test #9:
score: 10
Accepted
time: 21ms
memory: 115536kb
input:
40 9880 4 19 31 610502845 10 19 33 190412843 21 24 39 649028784 16 22 40 569593239 5 9 37 550862419 11 23 40 654613112 6 18 23 492267246 22 23 30 538715841 6 16 24 407919735 5 16 18 388907784 2 16 18 388907784 21 24 28 281403057 7 12 27 451830401 3 11 16 508407438 15 33 36 561955959 6 23 29 70605893...
output:
YES 877488996 197498120 508407438 610502845 209356929 706058934 655952999 624132238 550862419 32695410 654613112 72694954 399757770 396827347 561955959 407919735 779328631 388907784 190412843 657895429 832003778 569593239 492267246 32695410 718125822 812463588 451830401 281403057 877488996 538715841...
result:
ok solution is correct
Test #10:
score: 0
Accepted
time: 64ms
memory: 124716kb
input:
80 82160 8 15 41 111467584 35 54 58 471689837 51 66 69 545620573 20 63 76 46182451 15 34 40 54922534 19 27 49 410013534 6 13 18 849916477 3 12 30 436881726 8 23 54 239683045 6 37 40 544597112 29 52 70 792746131 7 52 75 478735558 11 50 74 735803963 4 28 50 415323204 23 54 68 347125331 33 67 70 525526...
output:
YES 325002529 459824851 295082589 415323204 815182959 942276740 478735558 111467584 372443066 865933468 870762944 436881726 849916477 838601559 30644239 942276740 236051181 278519554 906172939 46182451 284349661 777302867 514711056 91113251 393446574 393984539 410013534 478037910 848158501 839985283...
result:
ok solution is correct
Test #11:
score: 0
Accepted
time: 75ms
memory: 124832kb
input:
85 98770 27 63 76 248029292 25 30 35 550251757 48 53 54 313065504 4 25 37 610144939 74 75 85 456600945 21 75 79 276185205 8 11 84 490843403 19 42 64 531946207 16 30 81 443517377 8 50 68 108297273 51 53 83 535689817 20 35 74 550251757 3 10 63 602682982 3 41 75 456600945 59 77 83 737132984 27 55 71 24...
output:
YES 796868158 907723685 602682982 100984224 318471625 51502508 180796805 966425090 966425090 943508228 357852673 16220061 575720344 557367888 70281602 16220061 660516746 70390628 944390058 569820119 276185205 238004487 825967092 790137066 879681171 158633329 242047823 823251516 499099426 443517377 7...
result:
ok solution is correct
Test #12:
score: 0
Accepted
time: 64ms
memory: 124156kb
input:
85 98770 20 22 67 732656342 25 44 56 244626385 13 59 75 213697467 63 82 85 309272560 28 57 72 364782312 5 8 30 645939411 23 44 53 376754743 12 34 66 506119701 52 54 70 781735421 8 32 71 569597003 13 34 54 476762429 26 47 66 240658437 7 67 69 496620269 23 30 62 647373465 2 10 44 120620033 13 47 60 49...
output:
YES 853072217 84893870 84893870 744163096 645939411 830618471 496620269 496620269 200930742 120620033 380324990 506119701 49183774 530359747 530359747 718404242 606967479 113270399 861487950 175117549 732656342 732656342 376754743 244626385 244626385 240658437 464279351 364782312 54073243 647373465 ...
result:
ok solution is correct
Test #13:
score: 0
Accepted
time: 64ms
memory: 123528kb
input:
85 98770 21 32 83 503624580 20 39 69 305307880 44 45 57 876818763 10 25 41 522952359 19 62 71 613955167 54 63 74 177973416 6 61 71 360070176 51 52 60 541361998 13 33 46 503624580 2 43 73 68833128 12 55 63 459648386 45 66 67 521097301 29 45 76 307722318 2 19 43 82263839 37 62 69 193456165 54 62 77 53...
output:
YES 32323329 32323329 253295445 836531158 836531158 360070176 175567178 175567178 441708705 441708705 668511993 459648386 459648386 459648386 343676539 410730179 613955167 613955167 613955167 613955167 70655797 70655797 70655797 70655797 522952359 522952359 1538604 1538604 1538604 1538604 1538604 50...
result:
ok solution is correct
Test #14:
score: 0
Accepted
time: 64ms
memory: 124380kb
input:
85 98770 3 50 73 299752403 7 73 74 248077845 11 21 55 567953112 28 46 59 812646150 50 62 66 428307066 12 15 70 328727493 28 38 61 734761219 1 12 18 301543584 40 41 42 154591206 34 50 67 782539441 6 46 54 694114842 17 68 72 600618593 35 56 78 735071616 29 80 82 392386527 26 29 32 332472714 1 63 67 78...
output:
NO
result:
ok no solution
Test #15:
score: 0
Accepted
time: 59ms
memory: 123156kb
input:
85 98770 1 62 71 588317506 24 43 47 363838243 40 75 84 470529263 3 13 70 380819035 29 38 65 429982001 37 72 82 441727959 11 13 77 218506970 22 39 65 768340659 45 60 67 522712319 1 18 29 429982000 9 42 79 344491484 34 54 81 538619513 11 39 75 161544337 37 49 80 344491484 59 61 73 454057625 17 18 28 3...
output:
NO
result:
ok no solution
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #2:
100%
Accepted
Dependency #3:
0%