QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#50183 | #4809. Maximum Range | sealnot123# | WA | 88ms | 28160kb | C++ | 6.3kb | 2022-09-25 05:31:50 | 2022-09-25 05:31:53 |
Judging History
answer
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define rep(i,a,b) for(int i=a; i<(b); ++i)
#define FOR(i,a,b) for(int i=a; i<(b); ++i)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int N = 100005;
int n, m;
vector<vector<pii>> edge;
int cnt = 0;
int comp[N];
vvi node_in_comp;
vector<vector<pii>> edge_in_comp;
int t = 0;
int idx[N], lowlink[N];
stack<int> stk;
void dfs(int u, int p) {
idx[u] = lowlink[u] = ++t;
stk.push(u);
for(pii e: edge[u]) {
int v = e.x;
if(v == p) continue;
if(idx[v]) lowlink[u] = min(lowlink[u], idx[v]);
else {
dfs(v, u);
lowlink[u] = min(lowlink[u], lowlink[v]);
}
}
if(idx[u] == lowlink[u]) {
node_in_comp.eb();
while(1) {
int x = stk.top();
stk.pop();
comp[x] = cnt;
node_in_comp[cnt].eb(x);
if(x == u) break;
}
++cnt;
}
}
// =======================================================
ll max_range = -1e18;
vector<int> ans;
struct edge_ {
int v, cap, pos, num;
edge_(int _v, int _cap, int _pos, int _num) {
v = _v;
cap = _cap;
pos = _pos;
num = _num;
}
};
vector<vector<edge_>> g;
queue<int> bfs;
int dp[N], from[N];
int used[N];
int edge_count;
void add_edge(int a, int b, int c, bool oneway = false) {
int posa = sz(g[a]);
int posb = sz(g[b]);
g[a].eb(b, 1, posb, edge_count);
if(!oneway) g[b].eb(a, 1, posa, edge_count);
else g[b].eb(a, 0, posa, edge_count);
++edge_count;
}
void st(int source, int sink, int c) {
for(int e : node_in_comp[c]) {
dp[e] = -1;
from[e] = -1;
}
dp[sink] = from[sink] = -1;
dp[source] = 0;
from[source] = -1;
bfs.push(source);
while(!bfs.empty()) {
int u = bfs.front();
bfs.pop();
for(edge_ &e : g[u]) {
if(e.cap == 0) continue;
if(dp[e.v] != -1) continue;
dp[e.v] = dp[u]+1;
from[e.v] = u;
bfs.push(e.v);
}
}
}
void augment(int source, int sink) {
int now = sink;
assert(from[sink] != -1);
while(now != source) {
int next = from[now];
for(edge_ &e: g[next]) {
if(e.v == now) {
assert(e.cap > 0);
e.cap--;
g[now][e.pos].cap++;
used[e.num] ^= 1;
break;
}
}
now = next;
}
}
vi temp_path;
void dfs_path(int now) {
if(now < n) {
temp_path.pb(now);
}
for(edge_ &e: g[now]) {
if(used[e.num]) {
used[e.num] ^= 1;
dfs_path(e.v);
}
}
}
vi find_path(pair<pii,int> Max, pair<pii,int> Min) {
if(Max.x.x > Max.x.y) swap(Max.x.x, Max.x.y);
if(Min.x.x > Min.x.y) swap(Min.x.x, Min.x.y);
int cur = comp[Max.x.x];
int comp_sz = sz(node_in_comp[cur]);
int source = n;
int sink = n+1;
// add edge
for(int u : node_in_comp[cur]) {
for(auto e : edge_in_comp[u]) {
int v = e.x;
if(u > v) continue;
if(pii(u,v) == Max.x || pii(u,v) == Min.x) {
continue;
}
add_edge(u, v, 1);
}
}
add_edge(source, Max.x.x, 1, true);
add_edge(source, Max.x.y, 1, true);
add_edge(Min.x.x, sink, 1, true);
add_edge(Min.x.y, sink, 1, true);
// bfs twice
rep(i,0,2){
st(source, sink, cur);
augment(source, sink);
}
// find path
temp_path.clear();
dfs_path(source);
// TODO: clean up
rep(i, 0, edge_count) {
used[i] = 0;
}
edge_count = 0;
g[source].clear();
g[sink].clear();
for(int u : node_in_comp[cur]) {
g[u].clear();
}
// debug
/*
printf("Comp: ");
for(int u: node_in_comp[cur]) printf("%d ",u);
puts("");
printf("Max: (%d,%d),%d\n",Max.x.x,Max.x.y,Max.y);
printf("Min: (%d,%d),%d\n",Min.x.x,Min.x.y,Min.y);
printf("Path: ");
for(int u: temp_path) {
printf("%d ",u);
}
puts("");
*/
return temp_path;
}
void solve() {
scanf("%d %d",&n,&m);
edge.resize(n);
edge_in_comp.resize(n);
g.resize(n+2);
rep(i, 0, m) {
int a, b, c;
scanf("%d %d %d",&a,&b,&c);
--a;
--b;
edge[a].eb(b,c);
edge[b].eb(a,c);
}
dfs(0, -1);
rep(i, 0, cnt) {
if(sz(node_in_comp[i]) < 3) continue;
// find max edge, min edge
pair<pii,int> Max(pii(0,0),-(1<<30)), Min(pii(0,0),(1<<30));
for(int u : node_in_comp[i]) {
for(pii e : edge[u]) {
if(comp[e.x] == comp[u]) {
edge_in_comp[u].pb(e);
if(e.y > Max.y) Max = {pii(u,e.x),e.y};
if(e.y < Min.y) Min = {pii(u,e.x),e.y};
}
}
}
if(max_range < Max.y-Min.y) {
// Find path
if(Max.x == Min.x) {
bool found= false;
if(Max.x.x > Max.x.y) swap(Max.x.x,Max.x.y);
for(int u : node_in_comp[i]) {
for(pii e : edge[u]) {
if(comp[e.x] == comp[u]) {
int a = u;
int b = e.x;
if(a > b) swap(a,b);
if(pii(a,b) != Max.x){
Min.x = pii(a,b);
found = true;
break;
}
}
}
if(found) break;
}
}
ans = find_path(Max, Min);
max_range = Max.y-Min.y;
}
}
printf("%lld\n",max_range);
printf("%d\n",sz(ans));
for(int e : ans) printf("%d ",e+1);
}
int main() {
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3696kb
input:
5 7 1 2 1 1 3 -2 2 3 1 3 4 3 4 5 1 1 5 -1 2 5 2
output:
5 4 3 1 5 4
result:
ok ok
Test #2:
score: 0
Accepted
time: 55ms
memory: 21108kb
input:
99997 100000 12238 99016 352755196 99016 25485 -412473602 25485 2440 991507552 2440 31171 -181894654 36970 2440 -800167579 2440 41865 -148191946 96629 31171 847888506 36970 95740 395546542 27992 2440 647886610 99016 29557 369124914 80795 27992 -673871966 36970 3509 573208857 57672 29557 874406776 41...
output:
1959330954 37 94991 86274 74677 92617 86665 76022 72089 22074 96230 87712 51491 72825 3463 84407 67966 89628 84997 54073 68523 30288 88289 37694 96778 46301 34883 95092 31171 2440 25485 99016 29557 57672 69259 68883 44442 4697 96048
result:
ok ok
Test #3:
score: 0
Accepted
time: 56ms
memory: 21864kb
input:
99997 100000 41884 21178 -431811360 41884 42699 -450057006 36523 21178 582079730 21178 96679 615552614 63637 21178 498974417 96679 5108 235820276 75058 41884 220112636 35148 42699 589595309 36523 18002 -637739861 65854 5108 -312755792 45137 41884 -511118771 5108 31311 554050951 25335 35148 -28341059...
output:
1968439328 40 23692 87673 42699 41884 45137 85192 38202 83711 83919 55330 71151 98733 99716 70298 33264 26071 90144 25926 52252 51434 69337 7577 5108 50088 6204 28694 41126 87303 83047 26981 54901 59612 14678 35287 78274 18331 89860 71024 99686 98098
result:
ok ok
Test #4:
score: 0
Accepted
time: 64ms
memory: 21564kb
input:
99984 99999 33974 29867 335681778 33974 87468 348956829 83048 87468 320849805 29867 69456 -424530698 72457 69456 -950650074 53838 83048 755969166 85914 69456 569454441 51728 87468 -202158773 15970 29867 -865071002 15970 94894 697607001 94894 74694 616318126 33974 11496 -89287579 53838 34365 -6577379...
output:
1985932414 36 50114 35807 13570 79841 32897 75496 85914 55808 57640 58540 79605 55857 61993 46598 303 11395 92249 27866 23026 83298 1652 76013 29864 53838 83048 87468 51728 75902 5449 70238 97838 83656 91542 28078 78849 80694
result:
ok ok
Test #5:
score: 0
Accepted
time: 60ms
memory: 21108kb
input:
99988 99992 8584 11873 -811540160 68064 11873 -930246087 11873 60056 916668870 68064 82193 -859062523 60056 75072 790866030 27767 75072 357619485 75072 78221 411650300 39636 82193 264106928 6675 60056 933851261 71747 78221 -508471038 11873 92771 -665232168 34402 27767 -906494982 11873 42714 63734230...
output:
1932268861 30 6675 28745 99809 8778 38274 64174 34179 75176 25891 62720 16385 20678 83884 75593 93559 21107 26922 8975 89787 23798 83283 2518 50628 88236 5185 29873 3186 91957 75072 60056
result:
ok ok
Test #6:
score: 0
Accepted
time: 46ms
memory: 20764kb
input:
99996 99996 58191 98120 261718607 91298 98120 471683748 58191 68921 217652908 67441 91298 -731916804 78177 68921 810185021 98120 54747 -35446486 78177 2822 -409569426 91298 68058 -897038977 68921 39067 892161204 30165 78177 379543758 32418 98120 -139944101 11281 68921 422411872 37751 32418 331606200...
output:
1752928792 25 18913 85525 42296 25934 67249 16812 65221 81854 64478 74019 46983 4369 77560 30739 1917 58464 3308 3783 48440 58191 68921 11281 34081 78216 29915
result:
ok ok
Test #7:
score: 0
Accepted
time: 52ms
memory: 21072kb
input:
99996 100000 39127 4358 657531703 4358 66528 484843263 47215 4358 -856669390 47215 26179 -147254695 24822 39127 -635228854 81984 26179 600617794 24822 60559 327733708 39127 23879 286268283 95563 81984 -766366787 96587 24822 723252700 23879 13711 -303309809 60559 38379 992907085 60559 6012 -15086498 ...
output:
1948904917 51 38379 67362 37704 53517 23254 1066 28267 79904 54151 24450 79459 52647 10570 24822 39127 23879 13711 16150 60168 12024 27325 73608 58919 19383 92093 74141 3750 42006 67183 31390 97465 24485 4358 61378 82877 24890 38051 91154 63827 13465 90743 30145 41482 70789 91374 66385 37095 8030 96...
result:
ok ok
Test #8:
score: 0
Accepted
time: 43ms
memory: 21592kb
input:
99983 99998 360 38113 273639182 29807 360 -492749399 360 45494 960572841 67090 45494 -168787586 38113 61765 -90469418 71988 360 -556152065 67090 77653 704061103 30847 38113 542389160 84363 30847 295740326 30847 62591 -916431414 86104 77653 878763485 45494 11422 -795069866 86104 64096 714130240 61765...
output:
1972142685 35 64559 25273 47913 1904 50615 97340 8333 42546 32497 58830 58078 3710 93146 3381 46673 75450 28454 29807 67396 49296 2351 1877 74104 85692 24073 31895 12093 71599 84363 30847 38113 360 45494 67090 85762
result:
ok ok
Test #9:
score: 0
Accepted
time: 65ms
memory: 20960kb
input:
99991 99993 70785 63179 -402654804 91872 63179 -441007900 30847 70785 779215016 72954 63179 -228470351 92375 30847 534166099 49724 63179 -37611056 44235 70785 -443931516 38220 44235 -187234181 44235 63035 -237171010 30847 50624 118354734 92375 24980 -382011924 56418 50624 -658160541 50624 10991 -966...
output:
1793776773 23 31140 44630 73442 3092 58361 62402 66274 56013 57891 97526 53000 30214 85483 52773 86737 91872 63179 72954 40199 70428 9524 46153 84999
result:
ok ok
Test #10:
score: 0
Accepted
time: 64ms
memory: 21724kb
input:
99995 99997 93178 82375 -969044986 93178 19072 -204354005 35344 93178 172625135 93178 56390 -284098052 88798 19072 842699965 82375 24707 508376359 19072 71420 2142150 40446 93178 -437060610 40446 51377 -236216782 51377 89470 -349454494 19614 71420 -747727667 89470 14659 91615005 35344 49064 -7684125...
output:
1928930936 17 13782 6259 19871 82375 93178 40446 51377 3209 48876 53143 61912 65439 55069 80688 84372 3529 41657
result:
ok ok
Test #11:
score: 0
Accepted
time: 57ms
memory: 21288kb
input:
99984 99992 13417 15144 707033172 79217 13417 -472387862 26033 13417 -36135406 13417 16174 -89686765 16174 96840 613288820 13417 11444 -398371819 11444 41716 627519572 41716 5951 233568303 96840 41978 -755500822 55150 41716 715325856 41978 88656 816236450 15144 5839 644375332 88656 95763 878003222 6...
output:
1958415767 40 11993 93511 80696 35258 84539 78871 41533 72086 64840 71601 61488 1019 19346 20549 6162 15155 65480 95763 95939 39284 33954 92172 82891 26100 81816 24802 65474 44860 12538 28616 36613 4719 62781 15965 90176 17104 96840 16174 13417 26033
result:
ok ok
Test #12:
score: -100
Wrong Answer
time: 88ms
memory: 28160kb
input:
80000 98516 26903 1777 -924244496 60501 50043 -169932745 73857 9688 924119596 51789 37304 -395289958 66012 19584 677645038 36094 31329 -438857807 23716 36356 333796707 64800 10550 -272867916 24677 61533 -276717055 37159 23410 564922612 57429 13265 -535543043 53527 15651 304660186 13261 58532 2102669...
output:
1999981013 59626 55945 35610 33489 22956 37280 79643 71306 40096 5554 78997 11316 25051 25291 5554 37280 62056 58809 6365 3574 62056 11903 68116 37401 25291 57161 50170 42566 44274 11751 52409 42594 21406 11751 57161 23850 65862 3574 21213 51177 73528 52409 47295 21188 2409 73528 44843 43087 36973 7...
result:
wrong answer Edge 79643-71306 does not appear in original graph