Georeth's blog

By Georeth, history, 5 years ago, In English

SGU-151

Exactly the same code, GNU C++11 got WA on test #19 75830647, GNU C++14 got AC 75830595. I submitted 30 times to find the problem.

#include <cstdio>
#include <cmath>
static const double EPS = 1e-13;
int main() {
    double c, b, m; scanf("%lf%lf%lf", &c, &b, &m);
    double c2 = c * c, b2 = b * b, m2 = m * m;
    double a2 = 2 * (b2 + c2) - 4 * m2;
    if (a2 < 0) {
        printf("Mission impossible");
        return 0;
    }
    double a = sqrt(a2);
    if ((a + b < c) || (a + c < b) || (b + c < a)) {
        printf("Mission impossible");
        return 0;
    }
    double x = (c2 - b2) / (2 * a);
    if (fabs(a) < EPS) x = 0;
    double y = sqrt(m2 - x * x);
    printf("%.5lf %.5lf\n",x,y);
    printf("%.5lf %.5lf\n",-(a)/(double)2.0,(double)0);
    printf("%.5lf %.5lf",(a)/(double)2.0,(double)0);
    return 0;
}

I hope the Codeforces maintainers verify the test data and my report of SGU-124

Full text and comments »

  • Vote: I like it
  • -6
  • Vote: I do not like it

By Georeth, history, 5 years ago, In English

SGU-124

I solve this problem by counting the number of intersections of the closed broken line and ray from (x0,y0+0.5) to left, but got WA on test case #15. Then I changed the ray from (x0, y0+0.5) to right, and got AC.

I performed a sanity check on the test data, and the test passed first 14 test cases but failed on #15: the closed broken line is without self-crossings and self-contacts, so every endpoints appears exactly twice in the broken line.

I hope the Codeforces maintainers verify the test data.

Full text and comments »

  • Vote: I like it
  • +18
  • Vote: I do not like it

By Georeth, history, 8 years ago, In English

Hello, I made a very classic tree problem. I want to get some clean solutions, because my solution seems very complicated. I made this problem on Polygon, but cannot make it public to every one. So I publish this problem here.

I hope you can give me good solutions (maybe by ideone.com / or join my group).

I create a group called "problem sharing" at http://codeforces.me/group/t0m8sIZmgT. You can join this group to solve this problem.

Maximum weight vertex for a fixed distance
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Given a tree with n vertices and a positive integer D. Vertices are numbered from 1 to n. Each vertex u has a positive weight wu.

For each vertex u, compute ans[u] = max{wv: dist(u, v) = D}. if such vertex v does not exist, ans[u] =  - 1.

Where dist(u, v) is length of shortest path between u and v.

Input

First line contains integer n and D. (1 ≤ n ≤ 100000, 1 ≤ D ≤ 100).

Second line contains n integers w1, w2, ..., wn. (1 ≤ wi ≤ 109)

Then (n - 1) lines follow. Each line contains two integer u and v, which means there is an edge (u, v).

Output

Output n intergers in a single line. i-th of them should be ans[i].

Examples
Input
5 2
1 3 4 2 5
1 2
2 3
3 4
4 5
Output
4 2 5 3 4 
Input
5 2
1 3 7 2 5
1 5
2 5
3 5
4 5
Output
7 7 3 7 -1 

Full text and comments »

  • Vote: I like it
  • +55
  • Vote: I do not like it