# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
518780 |
2022-01-24T15:30:38 Z |
Wayne_Yan |
Graph (BOI20_graph) |
C++17 |
|
2 ms |
2636 KB |
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef int64_t ll;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define mid ((l+r)/2)
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng)
#define debug(x) (cerr << (#x) << " = " << x << "\n")
#define cmax(a,b) (a = max(a,b))
#define cmin(a,b) (a = min(a,b))
template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
inline long double f(pii p, long double s){
return s * p.ff + p.ss;
}
const int maxN = 1e5+10;
vector<pii> edge[maxN];
bool visited[maxN];
vector<pii> curr_poly;
long double eps = 1e-12;
long double val[maxN];
long double sub(long double x){
long double ans = 0;
for(pii p : curr_poly){
ans += fabsl(f(p, x));
}
return ans;
}
map<pii, int> chk;
long double ccx = 1e18;
pii poly[maxN];
long double subs;
void dfs(int c, int p){
visited[c] = true;
curr_poly.pb(poly[c]);
for(auto [i,x] : edge[c]){
if(i == p) continue;
pii target = {-poly[c].ff, x - poly[c].ss };
if(visited[i]){
pii orig = poly[i];
if(orig != target){
if(orig.ff == target.ff){
printf("NO");
exit(0);
}else{
long double nw = - ( 0.0 + orig.ss - target.ss) / ( 0.0 + orig.ff - target.ff);
if( ccx > 1e17 ){
ccx = nw;
}else{
if(fabsl(nw - ccx) > eps){
printf("NO");
exit(0);
}
}
}
}
}else{
poly[i] = target;
dfs(i, c);
}
}
}
bool visited_val[maxN];
void dfs_val(int c, int p){
visited_val[c] = true;
val[c] = (subs * poly[c].ff + poly[c].ss);
for(auto[i,x] : edge[c]){
if(i == p) continue;
if(visited_val[i]) continue;
dfs_val(i, c);
}
}
signed main(){
int n,m;
cin >> n >> m;
F(m){
int x,y,c;
cin >> x >> y >> c;
if(x > y) swap(x,y);
if(!chk[mp(x,y)]){
chk[mp(x,y)] = c;
}else{
if(chk[mp(x,y)] != c){
printf("NO");
exit(0);
}
}
edge[x].pb(mp(y, c));
edge[y].pb(mp(x, c));
}
Fl(i, 1, n+1){
if(visited[i]) continue;
poly[i] = {1, 0};
curr_poly.clear();
ccx = 1e18;
dfs(i, 0);
if(ccx > 1e17){
long double l = -1e6;
long double r = 1e6;
Fi(xxxxx, 200){
long double a = sub(mid);
long double b = sub(mid + 1e-14);
if(fabsl(a-b) < 1e-15){
break;
}else if(a > b){
l = mid;
}else{
r = mid;
}
}
subs = mid;
}else{
subs = ccx;
}
dfs_val(i, 0);
}
printf("YES\n");
Fl(i, 1, n+1){
printf("%.15Lf ", val[i]);
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2636 KB |
answer = YES |
2 |
Correct |
2 ms |
2636 KB |
answer = YES |
3 |
Incorrect |
1 ms |
2636 KB |
participant answer is larger than the answer of jury |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2636 KB |
answer = YES |
2 |
Correct |
2 ms |
2636 KB |
answer = YES |
3 |
Incorrect |
1 ms |
2636 KB |
participant answer is larger than the answer of jury |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2636 KB |
answer = YES |
2 |
Correct |
2 ms |
2636 KB |
answer = YES |
3 |
Incorrect |
1 ms |
2636 KB |
participant answer is larger than the answer of jury |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2636 KB |
answer = YES |
2 |
Correct |
2 ms |
2636 KB |
answer = YES |
3 |
Incorrect |
1 ms |
2636 KB |
participant answer is larger than the answer of jury |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2636 KB |
answer = YES |
2 |
Correct |
2 ms |
2636 KB |
answer = YES |
3 |
Incorrect |
1 ms |
2636 KB |
participant answer is larger than the answer of jury |
4 |
Halted |
0 ms |
0 KB |
- |