ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#215275 | #2437. 随机游走 | N | 100 | 999ms | 53940kb | C++11 | 2.7kb | 2024-11-27 22:26:38 | 2024-11-27 23:40:08 |
answer
//
// na 2437.cpp
// Competitive Programming
//
// Created by m2 on 2024/11/27.
//
#include <stdio.h>
#include <iostream>
#include <time.h>
#include <random>
using namespace std;
const int maxn = 5e5 + 5;
int n, m, s, ul[maxn], vl[maxn], wl[maxn];
bool vis[maxn], col[maxn];
double wsum[maxn], plist1[maxn], plist2[maxn];
double *lp = plist1, *np = plist2;
struct Edge{
int i, w; Edge *nxt;
Edge(int i, int w, Edge *nxt): i(i), w(w), nxt(nxt) {}
};
Edge *head[maxn];
inline void edge(int st, int en, int w){ head[st] = new Edge(en, w, head[st]); }
#define trav(x) for(Edge *e = head[x]; e != nullptr; e = e->nxt)
template<typename T> inline void rd(T &v){
v = 0; char r = getchar();
while(r - 48 >= 10u)
r = getchar();
while(r - 48 < 10u){
v = (v << 3) + (v << 1) + (r ^ 48);
r = getchar();
}
}
inline void sim(){
swap(lp, np);
for(int i = 1; i <= n; ++i)
np[i] = 0;
for(int i = 1; i <= n; ++i)
trav(i)
np[e->i] += lp[i] * (e->w / wsum[i]);
}
bool bi = true;
void dfs(int idx, bool nc){
if(vis[idx]){
if(col[idx] != nc)
bi = false;
return;
}
vis[idx] = true;
col[idx] = nc;
trav(idx) dfs(e->i, !nc);
}
inline void norm(){
double ps = 0;
for(int i = 1; i <= n; ++i)
ps += np[i];
for(int i = 1; i <= n; ++i)
np[i] /= ps;
}
int main(){
clock_t st = clock();
cin.tie(0)->sync_with_stdio(false);
rd(n); rd(m); rd(s);
for(int i = 0; i < m; ++i){
rd(ul[i]); rd(vl[i]); rd(wl[i]);
edge(ul[i], vl[i], wl[i]);
edge(vl[i], ul[i], wl[i]);
wsum[ul[i]] += wl[i];
wsum[vl[i]] += wl[i];
}
dfs(s, true);
// np[s] = 1;
// random_device rd;
// mt19937 rnd(rd());
// uniform_real_distribution<> dis(0.0, 1.0);
// for(int i = 1; i <= n; ++i)
// if(vis[i])
// np[i] = dis(rnd);
for(int i = 1; i <= n; ++i)
if(vis[i])
np[i] = wsum[i];
norm();
// for(int i = 1; i <= n; ++i)
// cerr << np[i] << ' ';
// cerr << endl;
// bool f = false;
// while(double(clock() - st) / CLOCKS_PER_SEC < 0.7 || f){
// sim();
// f = !f;
// }
// cerr << "BIPART? " << bi << endl;
if(bi){
double ps = 0;
for(int i = 1; i <= n; ++i)
if(col[i])
ps += np[i];
for(int i = 1; i <= n; ++i)
if(col[i])
printf("%.10f ", np[i] / ps);
else
printf("0 ");
}else{
for(int i = 1; i <= n; ++i)
printf("%.10f ", np[i]);
}
printf("\n");
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1292kb
input:
2 2 1 1 2 552418 2 1 687983
output:
1.0000000000 0
result:
ok 2 numbers
Test #2:
score: 10
Accepted
time: 0ms
memory: 1292kb
input:
15 20 6 1 4 828 2 4 337 3 14 927 5 8 390 6 3 646 7 4 48 9 5 349 10 4 485 11 4 620 12 4 276 13 4 714 ...
output:
0.0879033855 0.0333597307 0 0 0 0.0639477331 0.0929518907 0.0386062166 0.0345476143 0.0480102950 0.1...
result:
ok 15 numbers
Test #3:
score: 10
Accepted
time: 0ms
memory: 1292kb
input:
20 20 14 1 19 1746 2 17 3922 3 7 5216 4 18 5768 5 19 4 6 16 5240 8 14 7366 9 8 4420 10 20 8517 11 9 ...
output:
0.1317556522 0 0 0 0.0000502980 0.1327993361 0.1483665719 0 0.1738299424 0 0 0.0729446973 0.02474662...
result:
ok 20 numbers
Test #4:
score: 10
Accepted
time: 0ms
memory: 1296kb
input:
60 100 40 1 43 752739 2 1 861767 3 21 651385 4 28 364 5 58 949 6 15 267 7 57 247988 8 50 820601 9 14...
output:
0.0267208176 0.0280196811 0.0107934158 0.0000165339 0.0098863016 0.0000044190 0.0420015432 0.0135919...
result:
ok 60 numbers
Test #5:
score: 10
Accepted
time: 0ms
memory: 1300kb
input:
98 100 53 1 27 986351 2 56 454750 3 36 141367 4 56 344982 5 70 727802 6 24 509565 7 55 776053 8 59 3...
output:
0 0.0087000003 0 0.0065999857 0.0139238651 0.0097486876 0.0148469738 0.0155966565 0.0081356243 0.015...
result:
ok 98 numbers
Test #6:
score: 10
Accepted
time: 0ms
memory: 1476kb
input:
817 1926 733 1 629 1 2 215 1 3 248 1 4 130 1 5 469 1 6 682 1 7 776 1 8 110 1 9 415 1 10 321 1 11 303...
output:
0.0010384216 0.0015576324 0.0010384216 0.0018172378 0.0023364486 0.0012980270 0.0007788162 0.0015576...
result:
ok 817 numbers
Test #7:
score: 10
Accepted
time: 148ms
memory: 29872kb
input:
166666 300000 119635 1 91644 655718 2 54315 300393 3 112333 880100 4 3430 427450 5 127315 74466 6 95...
output:
0.0000112198 0.0000020028 0.0000127108 0.0000028500 0.0000052638 0.0000034816 0.0000056758 0.0000050...
result:
ok 166666 numbers
Test #8:
score: 10
Accepted
time: 340ms
memory: 53240kb
input:
400000 500000 363488 1 254054 843859 2 169299 701504 3 174552 479095 4 70702 852271 5 301016 4 6 830...
output:
0.0000031258 0.0000044913 0.0000046792 0.0000023619 0.0000000000 0.0000005829 0.0000031231 0.0000048...
result:
ok 400000 numbers
Test #9:
score: 10
Accepted
time: 147ms
memory: 50196kb
input:
500000 500000 342024 1 367282 471300 2 346217 948546 3 230072 336639 4 458846 88399 5 20450 217996 6...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 500000 numbers
Test #10:
score: 10
Accepted
time: 364ms
memory: 53940kb
input:
466666 500000 456939 1 304818 887447 2 55736 302299 3 283098 150863 4 424825 796422 5 99211 331398 6...
output:
0.0000052835 0.0000040518 0.0000005265 0.0000034901 0.0000047797 0.0000000000 0.0000020424 0.0000000...
result:
ok 466666 numbers