提出 #33834317

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ld;
#define int long long
const int INF32 = 1e9 + 6e7;
const lli INF64 = (1LL << 61) + 1e17;
const int MOD = 1e9 + 7;
const lli MH1 = 1022063089, MH2 = 2034417103, MH3 = 1090250123, MH4 = 2024491871;
//const __int128 MHP = 3206430037875328613, MHM = 3681348219576961379;
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
struct splitmix { // https://codeforces.com/blog/entry/62393
    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 = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
class Fraction {
private:
    lli p;
    lli q;
public:
    Fraction() {
        p = 0;
        q = 0;
    }
    Fraction(lli num) {
        p = num;
        q = 1;
    }
    Fraction(lli num, lli denum) {
        p = num;
        q = denum;
        check();
        signify();
    }
    ~Fraction() {}
    Fraction operator+(Fraction fr2) {
        check();
        fr2.check();
        return Fraction(fr2.q * p + q * fr2.p, q * fr2.q);
    }
    Fraction operator-(Fraction fr2) {
        check();
        fr2.check();
        return Fraction(fr2.q * p - q * fr2.p, q * fr2.q);
    }
    Fraction operator*(Fraction fr2) {
        check();
        fr2.check();
        return Fraction(p*fr2.p, q*fr2.q);
    }
    Fraction operator/(Fraction fr2) {
        check();
        fr2.check();
        return Fraction(p*fr2.q, q*fr2.p);
    }
    Fraction& operator+=(Fraction fr2) {
        (*this) = (*this) + fr2;
        return *this;
    }
    Fraction& operator-=(Fraction fr2) {
        (*this) = (*this) - fr2;
        return *this;
    }
    Fraction& operator*=(Fraction fr2) {
        (*this) = (*this) * fr2;
        return *this;
    }
    Fraction& operator/=(Fraction fr2) {
        (*this) = (*this) / fr2;
        return *this;
    }
    bool operator==(Fraction fr2) {
        check();
        fr2.check();
        return this->p*fr2.q == fr2.p*this->q;
    }
    bool operator!=(Fraction fr2) {
        return !((*this) == fr2);
    }
    friend bool operator<(const Fraction& fr1, const Fraction& fr2);
    friend bool operator<=(const Fraction& fr1, const Fraction& fr2);
    friend bool operator>(const Fraction& fr1, const Fraction& fr2);
    friend bool operator>=(const Fraction& fr1, const Fraction& fr2);
    Fraction operator-() {
        return Fraction(-p, q);
    }
    void check() {
        assert(q != 0);
    }
    void normalize() {
        check();
        lli bcd = __gcd(abs(p), abs(q));
        p /= bcd;
        q /= bcd;
        signify();
    }
    void signify() {
        check();
        if(p == 0) {
            q = 1;
        }
        if(q < 0) {
            p = -p;
            q = -q;
        }
    }
    ld eval() {
        check();
        return (ld)(p)/q;
    }
    lli fpart() {
        check();
        return p/q;
    }
    lli fpartnum() {
        check();
        return p - p/q*q;
    }
    void print() {
        check();
        cout << "[" << p << "/" << q << "] ";
    }
    void println() {
        check();
        cout << "[" << p << "/" << q << "]\n";
    }
};
bool operator<(const Fraction& fr1, const Fraction& fr2) {
    return fr1.p * fr2.q < fr2.p * fr1.q;
}
bool operator<=(const Fraction& fr1, const Fraction& fr2) {
    return fr1.p * fr2.q <= fr2.p * fr1.q;
}
bool operator>(const Fraction& fr1, const Fraction& fr2) {
    return fr1.p * fr2.q > fr2.p * fr1.q;
}
bool operator>=(const Fraction& fr1, const Fraction& fr2) {
    return fr1.p * fr2.q >= fr2.p * fr1.q;
}
class Mint {
private:
    int val;
public:
    Mint() {
        val = 0;
    }
    Mint(lli cval) {
        val = (cval % MOD) + MOD;
        if(val >= MOD) val -= MOD;
    }
    ~Mint() {}
    int binPower(lli a, lli b) {
        if(b < 0) return 0;
        lli res = 1;
        while(b > 0) {
            if(b & 1)
                res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return (int)res;
    }
    Mint invr(Mint mi2) {
        return Mint(binPower(mi2.val, MOD-2));
    }
    Mint& operator+=(const Mint& mi2) {
        val += mi2.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    Mint& operator-=(const Mint& mi2) {
        val -= mi2.val;
        if(val < 0) val += MOD;
        return *this;
    }
    Mint& operator*=(const Mint& mi2) {
        val = (lli)val * mi2.val % MOD;
        return *this;
    }
    Mint& operator/=(const Mint& mi2) {
        val = (lli)val * invr(mi2).val % MOD;
        return *this;
    }
    Mint& operator^=(lli pval) {
        if(pval == -1)
            val = invr(Mint(val)).val;
        else
            val = binPower(val, pval);
        return *this;
    }
    Mint operator+(const Mint& mi2) const {
        return Mint(*this) += mi2;
    }
    Mint operator-(const Mint& mi2) const {
        return Mint(*this) -= mi2;
    }
    Mint operator*(const Mint& mi2) const {
        return Mint(*this) *= mi2;
    }
    Mint operator/(const Mint& mi2) const {
        return Mint(*this) /= mi2;
    }
    Mint operator^(lli pval) const {
        return Mint(*this) ^= pval;
    }
    bool operator==(const Mint& mi2) const {
        return val == mi2.val;
    }
    bool operator!=(const Mint& mi2) const {
        return val != mi2.val;
    }
    Mint& operator++() {
        val += 1;
        if(val >= MOD) val -= MOD;
        return *this;
    }
    Mint& operator--() {
        val -= 1;
        if(val < 0) val += MOD;
        return *this;
    }
    Mint operator++(signed) {
        Mint prevval = *this;
        ++(*this);
        return prevval;
    }
    Mint operator--(signed) {
        Mint prevval = *this;
        --(*this);
        return prevval;
    }
    friend ostream& operator<<(ostream &out, const Mint &mi);
    friend istream& operator>>(istream &in, Mint &mi);
};
istream& operator>>(istream &in, Mint &mi) {
    long long inp;
    in >> inp;
    mi = Mint(inp);
    return in;
}
ostream& operator<<(ostream &out, const Mint &mi) {
    out << mi.val;
    return out;
}
class DSU {
private:
    vector<int> dsp;
    vector<int> dsz;
    int d_n;
public:
    DSU() {
        d_n = 0;
    }
    ~DSU() {}
    void build_dsu(int n) {
        d_n = n;
        dsp.resize(d_n + 1);
        dsz.resize(d_n + 1);
        for(int i = 0; i <= d_n; i++) {
            dsp[i] = i;
            dsz[i] = 1;
        }
    }
    int find_root(int v) {
        if(v == dsp[v]) return v;
        return dsp[v] = find_root(dsp[v]);
    }
    void unite_sets(int a, int b) {
        a = find_root(a);
        b = find_root(b);
        if(a == b) return;

        if(dsz[a] > dsz[b])
            swap(a, b);

        dsz[b] += dsz[a];
        dsp[a] = b;
    }
};
template<typename T>
class Fenwick {
private:
    vector<T> fenw;
    vector<T> arrfw;
    int f_n;
public:
    Fenwick() {
        f_n = 0;
    }
    Fenwick(int n) {
        f_n = n;
        fenw = vector<T>(f_n + 1, 0);
        arrfw = vector<T>(f_n + 1, 0);
    }
    ~Fenwick() {}
    T sump(int i) {
        T ans = 0;
        while(i >= 0) {
            ans += fenw[i];
            i = (i & (i + 1)) - 1;
        }
        return ans;
    }
    void incv(int i, T d) {
        arrfw[i] += d;
        while(i <= f_n) {
            fenw[i] += d;
            i = (i | (i + 1));
        }
    }
    void setv(int i, T v) {
        incv(i, v - arrfw[i]);
    }
    T getv(int i) {
        return arrfw[i];
    }
    T sumr(int l, int r) {
        return sump(r) - sump(l - 1);
    }
};
const int N = 105;

struct edge {
    int v;
    int flow;
    int cap;
};

edge edges[(N*N+1)*8];

vector<int> graph[N*N+1];
int ptr[N*N+1];
int dist[N*N+1];
int curInd = 0;

void addEdge(int v1, int v2, int cap) {
    edges[curInd] = {v2, 0, cap};
    edges[curInd+1] = {v1, cap, cap};
    graph[v1].push_back(curInd);
    graph[v2].push_back(curInd+1);
    curInd += 2;
}

bool bfs(int s, int t) {
    memset(ptr, 0, sizeof(ptr));
    memset(dist, 62, sizeof(dist));
    dist[s] = 1;
    queue<int> qq;
    qq.push(s);
    while(!qq.empty()) {
        int cur = qq.front();
        qq.pop();
        for(auto& i : graph[cur]) {
            if(edges[i].cap == edges[i].flow) continue;
            if(dist[edges[i].v] > N*N) {
                dist[edges[i].v] = dist[cur] + 1;
                qq.push(edges[i].v);
            }
        }
    }
    return dist[t] < N*N;
}

void dfs(int v, int t, int curFlow, int& addFlow, bool& finished) {
    if(v == t) {
        finished = true;
        addFlow = curFlow;
        return;
    }
    for(int i = ptr[v]; i < graph[v].size(); i++, ptr[v]++) {
        auto ee = edges[graph[v][i]];
        if(ee.flow == ee.cap) continue;
        if(dist[v] + 1 != dist[ee.v]) continue;
        dfs(ee.v, t, min(ee.cap - ee.flow, curFlow), addFlow, finished);
        if(finished) {
            edges[graph[v][i]].flow += addFlow;
            edges[graph[v][i] ^ 1].flow -= addFlow;
            return;
        }
    }
}

int dinic(int s, int t) {
    int maxFlow = 0;
    while(bfs(s, t)) {
        while(true) {
            int addFlow = 0;
            bool finished = false;
            dfs(s, t, INF32, addFlow, finished);
            if(addFlow == 0) break;
            maxFlow += addFlow;
        }
    }
    return maxFlow;
}
pair<int, int> aa[N];
bool isPrime(int c) {
    for(int i = 2; i*i <= c; i++) {
        if(c % i == 0)
            return false;
    }
    return true;
}
signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(15);
    srand(time(0));
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> aa[i].first >> aa[i].second;
    }

    map<pair<int, int>, int> dd;
    int ind = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(isPrime(aa[i].first + aa[j].first)) {
                addEdge(i, n+j, INF64);
            }
        }
    }

    for(int i = 1; i <= n; i++) {
        addEdge(0, i, aa[i].second);
    }
    for(int j = 1; j <= n; j++)
        addEdge(n+j, N*N, aa[j].second);

    lli ans = dinic(0, N*N);
    cout << ans/2 << "\n";
    return 0;
}

提出情報

提出日時
問題 G - Erasing Prime Pairs
ユーザ pavlovoleg4889
言語 C++ (GCC 9.2.1)
得点 600
コード長 11094 Byte
結果 AC
実行時間 33 ms
メモリ 4084 KiB

コンパイルエラー

./Main.cpp: In function ‘void dfs(long long int, long long int, long long int, long long int&, bool&)’:
./Main.cpp:380:27: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  380 |     for(int i = ptr[v]; i < graph[v].size(); i++, ptr[v]++) {
      |                         ~~^~~~~~~~~~~~~~~~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:427:9: warning: unused variable ‘ind’ [-Wunused-variable]
  427 |     int ind = 0;
      |         ^~~

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 600 / 600
結果
AC × 2
AC × 50
セット名 テストケース
Sample 00_sample_01.txt, 00_sample_02.txt
All 00_sample_01.txt, 00_sample_02.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 02_has_one_small_01.txt, 02_has_one_small_02.txt, 02_has_one_small_03.txt, 02_has_one_small_04.txt, 02_has_one_small_05.txt, 02_has_one_small_06.txt, 02_has_one_small_07.txt, 02_has_one_small_08.txt, 02_has_one_small_09.txt, 02_has_one_small_10.txt, 03_has_one_large_01.txt, 03_has_one_large_02.txt, 03_has_one_large_03.txt, 03_has_one_large_04.txt, 03_has_one_large_05.txt, 03_has_one_large_06.txt, 03_has_one_large_07.txt, 03_has_one_large_08.txt, 03_has_one_large_09.txt, 03_has_one_large_10.txt, 04_handmade_01.txt, 04_handmade_02.txt, 04_handmade_03.txt, 04_handmade_04.txt, 04_handmade_05.txt, 04_handmade_06.txt, 04_handmade_07.txt, 04_handmade_08.txt, 04_handmade_09.txt, 04_handmade_10.txt, 05_handmade2_01.txt, 05_handmade2_02.txt, 05_handmade2_03.txt, 05_handmade2_04.txt, 06_handmade3_01.txt, 06_handmade3_02.txt, 06_handmade3_03.txt, 06_handmade3_04.txt, 07_handmade4_01.txt, 07_handmade4_02.txt, 07_handmade4_03.txt, 07_handmade4_04.txt, 07_handmade4_05.txt
ケース名 結果 実行時間 メモリ
00_sample_01.txt AC 8 ms 3988 KiB
00_sample_02.txt AC 6 ms 3924 KiB
01_random_01.txt AC 4 ms 3868 KiB
01_random_02.txt AC 3 ms 3868 KiB
01_random_03.txt AC 5 ms 3936 KiB
01_random_04.txt AC 4 ms 3952 KiB
01_random_05.txt AC 13 ms 3932 KiB
02_has_one_small_01.txt AC 28 ms 4064 KiB
02_has_one_small_02.txt AC 30 ms 3988 KiB
02_has_one_small_03.txt AC 29 ms 4056 KiB
02_has_one_small_04.txt AC 28 ms 4048 KiB
02_has_one_small_05.txt AC 33 ms 4060 KiB
02_has_one_small_06.txt AC 31 ms 3976 KiB
02_has_one_small_07.txt AC 26 ms 4020 KiB
02_has_one_small_08.txt AC 28 ms 4084 KiB
02_has_one_small_09.txt AC 23 ms 4064 KiB
02_has_one_small_10.txt AC 28 ms 3964 KiB
03_has_one_large_01.txt AC 26 ms 4020 KiB
03_has_one_large_02.txt AC 32 ms 3968 KiB
03_has_one_large_03.txt AC 32 ms 4056 KiB
03_has_one_large_04.txt AC 30 ms 4028 KiB
03_has_one_large_05.txt AC 26 ms 4000 KiB
03_has_one_large_06.txt AC 28 ms 3932 KiB
03_has_one_large_07.txt AC 30 ms 3932 KiB
03_has_one_large_08.txt AC 24 ms 3992 KiB
03_has_one_large_09.txt AC 30 ms 3988 KiB
03_has_one_large_10.txt AC 26 ms 3996 KiB
04_handmade_01.txt AC 29 ms 4000 KiB
04_handmade_02.txt AC 28 ms 4004 KiB
04_handmade_03.txt AC 33 ms 4060 KiB
04_handmade_04.txt AC 32 ms 4052 KiB
04_handmade_05.txt AC 32 ms 4060 KiB
04_handmade_06.txt AC 30 ms 4060 KiB
04_handmade_07.txt AC 33 ms 4056 KiB
04_handmade_08.txt AC 28 ms 4064 KiB
04_handmade_09.txt AC 29 ms 4048 KiB
04_handmade_10.txt AC 32 ms 4064 KiB
05_handmade2_01.txt AC 7 ms 3928 KiB
05_handmade2_02.txt AC 4 ms 4012 KiB
05_handmade2_03.txt AC 4 ms 3888 KiB
05_handmade2_04.txt AC 2 ms 3948 KiB
06_handmade3_01.txt AC 3 ms 4012 KiB
06_handmade3_02.txt AC 4 ms 4008 KiB
06_handmade3_03.txt AC 6 ms 3892 KiB
06_handmade3_04.txt AC 3 ms 3920 KiB
07_handmade4_01.txt AC 2 ms 4008 KiB
07_handmade4_02.txt AC 3 ms 3892 KiB
07_handmade4_03.txt AC 4 ms 3948 KiB
07_handmade4_04.txt AC 4 ms 3956 KiB
07_handmade4_05.txt AC 5 ms 4008 KiB