QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#937018 | #1292. Circuit Board Design | KimeyJ | WA | 1ms | 4224kb | C++20 | 2.2kb | 2025-03-16 05:16:58 | 2025-03-16 05:16:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define forr(i, a, b) for(ll i = (ll) a; i < (ll) b; i++)
#define forn(i, n) forr(i, 0, n)
#define dforr(i,a,b) for(int i=int(b)-1;i>=int(a);--i)
#define dforn(i,n) for(int i = n-1; i>=0; i--)
#define pb push_back
#define fst first
#define snd second
#define ln '\n'
#define sz(c) ((int)c.size())
#define zero(v) memset(v, 0, sizeof(v))
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll MOD = 1e9 + 7;
const ll MAXN = 1009;
const ll INF = 9e18;
const ld EPS = 1e-9;
vi g[MAXN];
pair<double,double> pos[MAXN];
int vis[MAXN];
using my_clock=chrono::steady_clock;
mt19937_64 engine(my_clock::now().time_since_epoch().count());
double pick(){
return uniform_real_distribution{-1.0,0.0}(engine);
}
void dfs(int u, int signo) {
vis[u] = 1;
int cant = 0;
for(auto v : g[u]) if (!vis[v]) cant++;
double paso = 2.0/(cant+0.0);
if (signo == -1) paso = paso*(-1.0);
double dx = pick() * (signo*1.0);
//cout << u+1 << " " << dx << ln;
int pari = 0;
for(auto v : g[u]) {
if (!vis[v]) {
//cout << "u= " << u+1 << " v= " << v+1 << ln;
//cout << "xu= " << pos[u].fst << " yu= " << pos[u].snd << " dx= " << dx << ln;
double nX = pos[u].fst+dx;
int dire = (nX > pos[u].fst ? -1 : 1);
double nY = sqrt(1.0-(dx*dx))+pos[u].snd;
//cout << "nx= " << nX << " ny= " << nY << ln;
pos[v] = {nX,nY};
dfs(v,dire);
dx = dx + paso;
//if (pari%2 == 0) dx = dx - paso, pari++;
//else dx = dx * (-1.0), pari++;
if (dx < -1.0) dx = 1.0;
else if (dx > 1.0) dx = -1.0;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("input.txt","r",stdin);
int n;
cin >> n;
forn(_,n-1) {
int u,v;
cin >> u >> v;
u--; v--;
g[u].pb(v);
g[v].pb(u);
}
pos[0] = {0.0,0.0};
dfs(0,1);
forn(i,n) cout << setprecision(8) << fixed << pos[i].fst << " " << pos[i].snd << ln;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4224kb
input:
1000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 ...
output:
0.00000000 0.00000000 -0.89377243 0.44852073 -1.46289899 1.27077067 -1.73635176 2.23265610 -2.04973146 3.18228401 -2.20589316 4.17001551 -2.61318422 5.08331393 -3.44961476 5.63138686 -3.68729032 6.60273146 -4.21903941 7.44963341 -4.33724416 8.44262265 -5.17945164 8.98177621 -5.50481565 9.92736505 -5...
result:
ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 4096kb
input:
1000 65 761 553 278 364 774 438 818 222 364 880 271 926 557 121 179 725 62 181 676 986 285 910 186 607 389 66 15 874 248 51 113 443 68 64 312 227 216 539 518 749 678 836 886 948 84 292 829 777 448 392 570 639 953 211 327 561 938 480 441 727 83 958 773 714 804 675 488 848 981 728 808 440 444 398 752 ...
output:
0.00000000 0.00000000 -10.82937663 17.67992282 354.05635767 558.75728496 258.89241395 388.17343324 293.83670559 453.71626818 91.82223292 122.31794424 -141.24612115 222.74662414 218.87689137 325.56902776 -76.15504137 122.82813811 89.19676317 118.56617047 131.68595638 182.23125724 -65.00825685 107.763...
result:
ok
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 4224kb
input:
1000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 27 ...
output:
0.00000000 0.00000000 -0.36243079 0.93201069 0.63756921 0.77039308 -1.10900843 1.59730899 -0.10900843 1.89936642 1.29167604 1.52679526 0.29167604 1.70866698 -1.41676711 2.54877344 -0.41676711 2.31897509 -0.07182648 2.89867493 -1.07182648 2.16951711 2.04071208 2.18932451 1.04071208 2.49479169 -0.1995...
result:
wrong answer Edges 4-9 and 5-11 are too close: 0.000000000.