QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#937018#1292. Circuit Board DesignKimeyJWA 1ms4224kbC++202.2kb2025-03-16 05:16:582025-03-16 05:16:58

Judging History

This is the latest submission verdict.

  • [2025-03-16 05:16:58]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 4224kb
  • [2025-03-16 05:16:58]
  • Submitted

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.