QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#89442	#5251. Constellations	tom0727	WA	4225ms	157040kb	C++14	7.0kb	2023-03-20 07:45:32	2023-03-20 07:45:36

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-03-20 07:45:36]
评测

测评结果：WA
用时：4225ms
内存：157040kb

查看

[2023-03-20 07:45:32]
提交

answer

#include <bits/stdc++.h>

using namespace std;

#if __cplusplus >= 201103L
    struct pairhash {
        static uint64_t splitmix64(uint64_t x) {
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }

        template<class T, class U>
        size_t operator() (const pair<T,U> &p) const {
            static const uint64_t FIXED_RANDOM = (uint64_t)chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(p.first + FIXED_RANDOM) ^ splitmix64(p.second+ FIXED_RANDOM);
        }
    };
    struct custom_hash {
        static uint64_t splitmix64(uint64_t x) {
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }

        size_t operator()(uint64_t x) const {
            static const uint64_t FIXED_RANDOM = (uint64_t)chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(x + FIXED_RANDOM);
        }
    };
    mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
    inline int randint(int l, int r) {
        return uniform_int_distribution<int>(l,r)(rng);
    }
    inline double randdouble(double l, double r) {
        return uniform_real_distribution<double>(l,r)(rng);
    }
#endif
 
#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) 0
#endif

#define fastio ios::sync_with_stdio(false); cin.tie(0);
#define ll long long
#define ull unsigned long long
#define ll128 __int128_t
#define PI 3.14159265358979323846
#define abs(a) ((a>0)?a:-(a))
#define pii pair<int,int>
#define pll pair<ll,ll>

const long double pi = acos(-1.0);
const long double eps = (double)1e-8;

const int mod = 998244353;

template<class T>
T qpow(T a, int b) {
    T res = 1;
    while (b) {
        if (b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}
int norm(int x) {
    if (x < 0) {
        x += mod;
    }
    if (x >= mod) {
        x -= mod;
    }
    return x;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(ll x) : x(norm((int)(x % mod))) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(mod - x));
    }
    Z inv() const {
        assert(x != 0);
        return qpow(*this, mod - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = (ll)(x) * rhs.x % mod;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        ll v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};

const int maxn = 2e3+5;
const int maxm = (500*500+105) * 2;

int par[maxn], sz[maxn];
int finds(int u) {
    if (par[u] == u) return u;
    return par[u] = finds(par[u]);
}

int id;
int age[maxn];
ll dis[maxn][maxn];
ll getdis(int a, int b) {
    return dis[min(a,b)][max(a,b)];
}

struct Node {
    ll d;
    int a, b;
    bool operator<(const Node& other) const {
        int pa = finds(a), pb = finds(b);
        int na = finds(other.a), nb = finds(other.b);
        ll d1 = d * sz[na] * sz[nb], d2 = other.d * sz[pa] * sz[pb];
        if (d1 == d2) {
            return (pii){min(age[pa], age[pb]), max(age[pa], age[pb])} > (pii){min(age[na], age[nb]), max(age[na], age[nb])};
        }
        return d1 > d2;
    }
};
int n, x[maxn], y[maxn];
priority_queue<Node> pq;
void clearall(int u) {
    sz[u] = 0;
    for (int v = u+1; v <= n; v++) dis[u][v] = 0;
}
bool unions(int u, int v) {
    u = finds(u), v = finds(v);
    if (u == v) return 0;
    if (sz[u] > sz[v]) {
        par[v] = u;
        sz[u] += sz[v];
        sz[v] = 0;
        // clearall(v);
    } else {
        par[u] = v;
        sz[v] += sz[u];
        sz[u] = 0;
        // clearall(u);
    }
    return 1;
}
inline ll sq(int x) {return x*x;}
ll cal(int i, int j) {
    return sq(x[i] - x[j]) + sq(y[i] - y[j]);
}
void printpq() {
    priority_queue<Node> tmp = pq;
    printf("pq = {");
    while (tmp.size()) {
        printf("(%d,%d),",tmp.top().a, tmp.top().b);
        tmp.pop();
    }
    printf("}\n");
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) par[i] = i, sz[i] = 1, cin >> x[i] >> y[i], age[i] = ++id;
    for (int i = 1; i <= n; i++) {
        for (int j = i+1; j <= n; j++) {
            dis[i][j] = cal(i,j);
            pq.push({cal(i,j), i, j});
        }
    }

    int cnt = 0;
    while (cnt < n-1) {
        Node nd = pq.top(); pq.pop();
        if (finds(nd.a) == finds(nd.b)) continue;
        if (nd.a != finds(nd.a) || nd.b != finds(nd.b)) continue;
        if (getdis(nd.a,nd.b) != nd.d) continue;

        int a = nd.a, b = nd.b;
        // printf("a = %d, b = %d\n",finds(a),finds(b));
        // a = finds(a), b = finds(b);
        // LOG(getdis(1, 3));
        // LOG(getdis(2, 3));
        // LOG(getdis(3, 4));

        unions(a, b);
        age[finds(a)] = ++id;
        for (int c = 1; c <= n; c++) {
            if (finds(c) == finds(a) || finds(c) == finds(b)) continue;
            int pc = finds(c);
            // printf("a = %d, b = %d, pc = %d, getdis(a,pc) = %lld, getdis(b,pc) = %lld\n",a,b,pc,getdis(a,pc),getdis(b,pc));
            int pa = finds(a);
            dis[min(pa, pc)][max(pa, pc)] = getdis(a, pc) + getdis(b, pc);
            // LOG(pc);
            // LOG(dis[min(a, pc)][max(a, pc)]);
            // LOG(getdis(a, pc));
            // dis[min(a, pc)][max(a, pc)] + dis[min(b, pc)][max(b, pc)];
            // dis[min(b, pc)][max(b, pc)] = getdis(a, pc);
            // pq.push({dis[min(a, pc)][max(a, pc)], a, pc});
        }
        for (int c = 1; c <= n; c++) {
            int pc = finds(c), pa = finds(a);
            if (pc == finds(a) || pc == finds(b)) continue;
            pq.push({getdis(pa, pc), min(pa, pc), max(pa, pc)});
            // LOG(pc);
        }

        cout << sz[finds(a)] << endl;
        // LOG(getdis(2, 3));
        // LOG(getdis(3, 4));
        cnt++;
        // printpq();
    }
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3332kb

input:

2
0 0
1 0

output:

result:

ok single line: '2'

Test #2:

score: -100

Wrong Answer

time: 4225ms

memory: 157040kb

input:

output:

result:

wrong answer 1500th lines differ - expected: '4', found: '6'