# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
906384 |
2024-01-14T07:23:20 Z |
MON |
Graph (BOI20_graph) |
C++14 |
|
21 ms |
4128 KB |
#include<iostream>
#include<random>
#include<ctime>
#include<vector>
#include<bitset>
#include<iomanip>
#include<algorithm>
using namespace std;
using pii = pair<int,int>;
using pid = pair<int,double>;
const double bulan[] = {0,0.25,-0.25,-0.5,0.5,-0.75,0.75,-1,1,-1.25,1.25,-1.5,1.5,-1.75,1.75,-2,2,2.5,-2.5,2.75,-2.75,3,-3,3.5,-3.5,4,-4,
4.5,-4.5,-5,5,-5.5,5.5,-6,6,-6.5,6.5,-7,7};
constexpr double eps = 1e-6;
constexpr int NMAX = 1e5 + 1;
mt19937 rng(time(nullptr));
bitset<NMAX> viz,fix; double ans[NMAX];
vector<pii> vecini[NMAX];
void dfs(int a,vector<int> &u)
{
u.emplace_back(a); viz[a] = 1;
for(auto &it : vecini[a])
if(!viz[it.first]) dfs(it.first,u);
}
int rnd(int it,uniform_int_distribution<int> &d)
{
int res = 1e9; while(it--) res = min(res,d(rng));
return res;
}
void go(int a,double v,vector<pid> &res)
{
res.push_back({a,v}); viz[a] = 1; ans[a] = v;
for(auto &it : vecini[a])
{
if(!viz[it.first])
go(it.first,it.second - v,res);
}
}
long double ab(vector<pid> &h)
{
long double res = 0;
for(auto &it : h) res += abs(it.second);
return res;
}
bool ok(vector<int> &h)
{
for(auto &f : h)
{
for(auto &s : vecini[f])
{
if(abs(ans[f] + ans[s.first] - s.second) > eps)
return 0;
}
}
return 1;
}
void solve(vector<int> &comp)
{
for(auto &v : comp)
{
if(fix[v])
{
vector<pid> h; go(v,ans[v],h);
for(auto &it : h) ans[it.first] = it.second;
return;
}
}
long double mini = 1e18; vector<pid> res;
uniform_int_distribution<int> d(0,(comp.size()-1) / 2); sort(comp.begin(),comp.end(),[](int &a,int &b){return vecini[a].size() < vecini[b].size();});
int mumu = comp[rnd(2,d)];
for(auto &val : bulan)
{
for(auto &it : comp) viz[it] = 0;
vector<pid> h; go(mumu,val,h); double now = ab(h);
if(now < mini && ok(comp))
{
mini = now;
res.swap(h);
}
}
for(auto &it : res)
ans[it.first] = it.second;
}
int main()
{
int n,m,a,b,c; cin >> n >> m;
for(int i = 1; i <= m ; i++)
{
cin >> a >> b >> c;
vecini[a].push_back({b,c});
vecini[b].push_back({a,c});
if(a == b)
{
fix[a] = 1;
ans[a] = (1.0 * c / 2);
}
}
vector<vector<int>> comps;
for(int i = 1; i <= n ; i++)
{
if(!viz[i])
{
vector<int> comp;
dfs(i,comp); comps.push_back(comp);
}
}
viz.reset();
for(auto &it : comps)
solve(it);
bool okk = 1;
for(auto &c : comps) okk &= ok(c);
if(!okk) cout << "NO";
else
{
cout << "YES\n";
for(int i = 1; i <= n ; i++)
cout << fixed << setprecision(2) << ans[i] << " ";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2648 KB |
answer = YES |
2 |
Correct |
1 ms |
2648 KB |
answer = YES |
3 |
Correct |
1 ms |
2652 KB |
answer = YES |
4 |
Correct |
1 ms |
2652 KB |
answer = NO |
5 |
Correct |
1 ms |
2652 KB |
answer = YES |
6 |
Correct |
1 ms |
2652 KB |
answer = YES |
7 |
Correct |
2 ms |
2804 KB |
answer = YES |
8 |
Correct |
1 ms |
2652 KB |
answer = YES |
9 |
Correct |
1 ms |
2652 KB |
answer = NO |
10 |
Correct |
1 ms |
2652 KB |
answer = YES |
11 |
Correct |
1 ms |
2652 KB |
answer = YES |
12 |
Correct |
1 ms |
2652 KB |
answer = NO |
13 |
Correct |
2 ms |
2652 KB |
answer = YES |
14 |
Correct |
1 ms |
2652 KB |
answer = YES |
15 |
Correct |
1 ms |
2652 KB |
answer = YES |
16 |
Correct |
1 ms |
2652 KB |
answer = YES |
17 |
Correct |
1 ms |
2652 KB |
answer = YES |
18 |
Correct |
1 ms |
2652 KB |
answer = YES |
19 |
Correct |
1 ms |
2652 KB |
answer = YES |
20 |
Correct |
1 ms |
2652 KB |
answer = YES |
21 |
Correct |
1 ms |
2652 KB |
answer = YES |
22 |
Correct |
1 ms |
2664 KB |
answer = NO |
23 |
Correct |
1 ms |
2652 KB |
answer = NO |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2648 KB |
answer = YES |
2 |
Correct |
1 ms |
2648 KB |
answer = YES |
3 |
Correct |
1 ms |
2652 KB |
answer = YES |
4 |
Correct |
1 ms |
2652 KB |
answer = NO |
5 |
Correct |
1 ms |
2652 KB |
answer = YES |
6 |
Correct |
1 ms |
2652 KB |
answer = YES |
7 |
Correct |
2 ms |
2804 KB |
answer = YES |
8 |
Correct |
1 ms |
2652 KB |
answer = YES |
9 |
Correct |
1 ms |
2652 KB |
answer = NO |
10 |
Correct |
1 ms |
2652 KB |
answer = YES |
11 |
Correct |
1 ms |
2652 KB |
answer = YES |
12 |
Correct |
1 ms |
2652 KB |
answer = NO |
13 |
Correct |
2 ms |
2652 KB |
answer = YES |
14 |
Correct |
1 ms |
2652 KB |
answer = YES |
15 |
Correct |
1 ms |
2652 KB |
answer = YES |
16 |
Correct |
1 ms |
2652 KB |
answer = YES |
17 |
Correct |
1 ms |
2652 KB |
answer = YES |
18 |
Correct |
1 ms |
2652 KB |
answer = YES |
19 |
Correct |
1 ms |
2652 KB |
answer = YES |
20 |
Correct |
1 ms |
2652 KB |
answer = YES |
21 |
Correct |
1 ms |
2652 KB |
answer = YES |
22 |
Correct |
1 ms |
2664 KB |
answer = NO |
23 |
Correct |
1 ms |
2652 KB |
answer = NO |
24 |
Correct |
1 ms |
2648 KB |
answer = YES |
25 |
Correct |
1 ms |
2652 KB |
answer = YES |
26 |
Correct |
1 ms |
2652 KB |
answer = YES |
27 |
Correct |
1 ms |
2648 KB |
answer = YES |
28 |
Correct |
1 ms |
2652 KB |
answer = YES |
29 |
Correct |
1 ms |
2652 KB |
answer = YES |
30 |
Correct |
1 ms |
2652 KB |
answer = NO |
31 |
Correct |
1 ms |
2652 KB |
answer = YES |
32 |
Correct |
1 ms |
2652 KB |
answer = YES |
33 |
Correct |
1 ms |
2676 KB |
answer = YES |
34 |
Correct |
1 ms |
2652 KB |
answer = YES |
35 |
Correct |
1 ms |
2652 KB |
answer = YES |
36 |
Correct |
1 ms |
2652 KB |
answer = YES |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2648 KB |
answer = YES |
2 |
Correct |
1 ms |
2648 KB |
answer = YES |
3 |
Correct |
1 ms |
2652 KB |
answer = YES |
4 |
Correct |
1 ms |
2652 KB |
answer = NO |
5 |
Correct |
1 ms |
2652 KB |
answer = YES |
6 |
Correct |
1 ms |
2652 KB |
answer = YES |
7 |
Correct |
2 ms |
2804 KB |
answer = YES |
8 |
Correct |
1 ms |
2652 KB |
answer = YES |
9 |
Correct |
1 ms |
2652 KB |
answer = NO |
10 |
Correct |
1 ms |
2652 KB |
answer = YES |
11 |
Correct |
1 ms |
2652 KB |
answer = YES |
12 |
Correct |
1 ms |
2652 KB |
answer = NO |
13 |
Correct |
2 ms |
2652 KB |
answer = YES |
14 |
Correct |
1 ms |
2652 KB |
answer = YES |
15 |
Correct |
1 ms |
2652 KB |
answer = YES |
16 |
Correct |
1 ms |
2652 KB |
answer = YES |
17 |
Correct |
1 ms |
2652 KB |
answer = YES |
18 |
Correct |
1 ms |
2652 KB |
answer = YES |
19 |
Correct |
1 ms |
2652 KB |
answer = YES |
20 |
Correct |
1 ms |
2652 KB |
answer = YES |
21 |
Correct |
1 ms |
2652 KB |
answer = YES |
22 |
Correct |
1 ms |
2664 KB |
answer = NO |
23 |
Correct |
1 ms |
2652 KB |
answer = NO |
24 |
Correct |
1 ms |
2648 KB |
answer = YES |
25 |
Correct |
1 ms |
2652 KB |
answer = YES |
26 |
Correct |
1 ms |
2652 KB |
answer = YES |
27 |
Correct |
1 ms |
2648 KB |
answer = YES |
28 |
Correct |
1 ms |
2652 KB |
answer = YES |
29 |
Correct |
1 ms |
2652 KB |
answer = YES |
30 |
Correct |
1 ms |
2652 KB |
answer = NO |
31 |
Correct |
1 ms |
2652 KB |
answer = YES |
32 |
Correct |
1 ms |
2652 KB |
answer = YES |
33 |
Correct |
1 ms |
2676 KB |
answer = YES |
34 |
Correct |
1 ms |
2652 KB |
answer = YES |
35 |
Correct |
1 ms |
2652 KB |
answer = YES |
36 |
Correct |
1 ms |
2652 KB |
answer = YES |
37 |
Correct |
2 ms |
2648 KB |
answer = YES |
38 |
Correct |
1 ms |
2652 KB |
answer = YES |
39 |
Correct |
2 ms |
2804 KB |
answer = YES |
40 |
Correct |
3 ms |
2908 KB |
answer = YES |
41 |
Correct |
2 ms |
2652 KB |
answer = NO |
42 |
Correct |
3 ms |
2908 KB |
answer = YES |
43 |
Correct |
3 ms |
2652 KB |
answer = YES |
44 |
Correct |
3 ms |
2652 KB |
answer = YES |
45 |
Correct |
3 ms |
2720 KB |
answer = YES |
46 |
Correct |
2 ms |
2652 KB |
answer = YES |
47 |
Correct |
2 ms |
2652 KB |
answer = YES |
48 |
Correct |
2 ms |
2908 KB |
answer = YES |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2648 KB |
answer = YES |
2 |
Correct |
1 ms |
2648 KB |
answer = YES |
3 |
Correct |
1 ms |
2652 KB |
answer = YES |
4 |
Correct |
1 ms |
2652 KB |
answer = NO |
5 |
Correct |
1 ms |
2652 KB |
answer = YES |
6 |
Correct |
1 ms |
2652 KB |
answer = YES |
7 |
Correct |
2 ms |
2804 KB |
answer = YES |
8 |
Correct |
1 ms |
2652 KB |
answer = YES |
9 |
Correct |
1 ms |
2652 KB |
answer = NO |
10 |
Correct |
1 ms |
2652 KB |
answer = YES |
11 |
Correct |
1 ms |
2652 KB |
answer = YES |
12 |
Correct |
1 ms |
2652 KB |
answer = NO |
13 |
Correct |
2 ms |
2652 KB |
answer = YES |
14 |
Correct |
1 ms |
2652 KB |
answer = YES |
15 |
Correct |
1 ms |
2652 KB |
answer = YES |
16 |
Correct |
1 ms |
2652 KB |
answer = YES |
17 |
Correct |
1 ms |
2652 KB |
answer = YES |
18 |
Correct |
1 ms |
2652 KB |
answer = YES |
19 |
Correct |
1 ms |
2652 KB |
answer = YES |
20 |
Correct |
1 ms |
2652 KB |
answer = YES |
21 |
Correct |
1 ms |
2652 KB |
answer = YES |
22 |
Correct |
1 ms |
2664 KB |
answer = NO |
23 |
Correct |
1 ms |
2652 KB |
answer = NO |
24 |
Correct |
1 ms |
2648 KB |
answer = YES |
25 |
Correct |
1 ms |
2652 KB |
answer = YES |
26 |
Correct |
1 ms |
2652 KB |
answer = YES |
27 |
Correct |
1 ms |
2648 KB |
answer = YES |
28 |
Correct |
1 ms |
2652 KB |
answer = YES |
29 |
Correct |
1 ms |
2652 KB |
answer = YES |
30 |
Correct |
1 ms |
2652 KB |
answer = NO |
31 |
Correct |
1 ms |
2652 KB |
answer = YES |
32 |
Correct |
1 ms |
2652 KB |
answer = YES |
33 |
Correct |
1 ms |
2676 KB |
answer = YES |
34 |
Correct |
1 ms |
2652 KB |
answer = YES |
35 |
Correct |
1 ms |
2652 KB |
answer = YES |
36 |
Correct |
1 ms |
2652 KB |
answer = YES |
37 |
Correct |
2 ms |
2648 KB |
answer = YES |
38 |
Correct |
1 ms |
2652 KB |
answer = YES |
39 |
Correct |
2 ms |
2804 KB |
answer = YES |
40 |
Correct |
3 ms |
2908 KB |
answer = YES |
41 |
Correct |
2 ms |
2652 KB |
answer = NO |
42 |
Correct |
3 ms |
2908 KB |
answer = YES |
43 |
Correct |
3 ms |
2652 KB |
answer = YES |
44 |
Correct |
3 ms |
2652 KB |
answer = YES |
45 |
Correct |
3 ms |
2720 KB |
answer = YES |
46 |
Correct |
2 ms |
2652 KB |
answer = YES |
47 |
Correct |
2 ms |
2652 KB |
answer = YES |
48 |
Correct |
2 ms |
2908 KB |
answer = YES |
49 |
Correct |
21 ms |
3812 KB |
answer = YES |
50 |
Incorrect |
20 ms |
4128 KB |
jury has the better answer: jans = YES, pans = NO |
51 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2648 KB |
answer = YES |
2 |
Correct |
1 ms |
2648 KB |
answer = YES |
3 |
Correct |
1 ms |
2652 KB |
answer = YES |
4 |
Correct |
1 ms |
2652 KB |
answer = NO |
5 |
Correct |
1 ms |
2652 KB |
answer = YES |
6 |
Correct |
1 ms |
2652 KB |
answer = YES |
7 |
Correct |
2 ms |
2804 KB |
answer = YES |
8 |
Correct |
1 ms |
2652 KB |
answer = YES |
9 |
Correct |
1 ms |
2652 KB |
answer = NO |
10 |
Correct |
1 ms |
2652 KB |
answer = YES |
11 |
Correct |
1 ms |
2652 KB |
answer = YES |
12 |
Correct |
1 ms |
2652 KB |
answer = NO |
13 |
Correct |
2 ms |
2652 KB |
answer = YES |
14 |
Correct |
1 ms |
2652 KB |
answer = YES |
15 |
Correct |
1 ms |
2652 KB |
answer = YES |
16 |
Correct |
1 ms |
2652 KB |
answer = YES |
17 |
Correct |
1 ms |
2652 KB |
answer = YES |
18 |
Correct |
1 ms |
2652 KB |
answer = YES |
19 |
Correct |
1 ms |
2652 KB |
answer = YES |
20 |
Correct |
1 ms |
2652 KB |
answer = YES |
21 |
Correct |
1 ms |
2652 KB |
answer = YES |
22 |
Correct |
1 ms |
2664 KB |
answer = NO |
23 |
Correct |
1 ms |
2652 KB |
answer = NO |
24 |
Correct |
1 ms |
2648 KB |
answer = YES |
25 |
Correct |
1 ms |
2652 KB |
answer = YES |
26 |
Correct |
1 ms |
2652 KB |
answer = YES |
27 |
Correct |
1 ms |
2648 KB |
answer = YES |
28 |
Correct |
1 ms |
2652 KB |
answer = YES |
29 |
Correct |
1 ms |
2652 KB |
answer = YES |
30 |
Correct |
1 ms |
2652 KB |
answer = NO |
31 |
Correct |
1 ms |
2652 KB |
answer = YES |
32 |
Correct |
1 ms |
2652 KB |
answer = YES |
33 |
Correct |
1 ms |
2676 KB |
answer = YES |
34 |
Correct |
1 ms |
2652 KB |
answer = YES |
35 |
Correct |
1 ms |
2652 KB |
answer = YES |
36 |
Correct |
1 ms |
2652 KB |
answer = YES |
37 |
Correct |
2 ms |
2648 KB |
answer = YES |
38 |
Correct |
1 ms |
2652 KB |
answer = YES |
39 |
Correct |
2 ms |
2804 KB |
answer = YES |
40 |
Correct |
3 ms |
2908 KB |
answer = YES |
41 |
Correct |
2 ms |
2652 KB |
answer = NO |
42 |
Correct |
3 ms |
2908 KB |
answer = YES |
43 |
Correct |
3 ms |
2652 KB |
answer = YES |
44 |
Correct |
3 ms |
2652 KB |
answer = YES |
45 |
Correct |
3 ms |
2720 KB |
answer = YES |
46 |
Correct |
2 ms |
2652 KB |
answer = YES |
47 |
Correct |
2 ms |
2652 KB |
answer = YES |
48 |
Correct |
2 ms |
2908 KB |
answer = YES |
49 |
Correct |
21 ms |
3812 KB |
answer = YES |
50 |
Incorrect |
20 ms |
4128 KB |
jury has the better answer: jans = YES, pans = NO |
51 |
Halted |
0 ms |
0 KB |
- |