11070번: Pythagorean Expectation

https://www.acmicpc.net/problem/11070

구현문제

시간복잡도는 테스트 케이스마다 $O(n+m)$

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, u, v, p, q, t;
int main() {
    for (scanf("%d", &t); t--;) {
        int s[1001] = {}, a[1001] = {}, maxi = 0, mini = 1e3;
        for (scanf("%d%d", &n, &m); m--;) {
            scanf("%d%d%d%d", &u, &v, &p, &q);
            s[u] += p; a[u] += q;
            s[v] += q; a[v] += p;
        }
        for (int i = 1; i <= n; i++) {
            int w = s[i] ? s[i] * s[i] * 1000LL / (s[i] * s[i] + a[i] * a[i]) : 0;
            if (w > maxi) maxi = w;
            if (w < mini) mini = w;
        }
        printf("%d\n%d\n", maxi, mini);
    }
    return 0;
}