QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#128480#2760. Simurghsomethingnew#0 0ms3812kbC++209.5kb2023-07-21 06:34:192024-07-04 00:50:44

Judging History

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

  • [2024-07-04 00:50:44]
  • 评测
  • 测评结果：0
  • 用时：0ms
  • 内存：3812kb
查看
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-21 06:34:19]
  • 提交

answer

//  ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
//  ➡ @roadfromroi ⬅
//  ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#include "simurgh.h"
#define all(x) x.begin(), x.end()
using namespace std;
struct dsu {
    vector<int> p;
    dsu(int n) {
        p.assign(n, {});
        for (int i = 0; i < n; ++i) {
            p[i] = i;
        }
    }
    int getv(int v) {
        if (p[v] == v)
            return v;
        return p[v] = getv(p[v]);
    }
    bool merge(int a, int b) {
        a = getv(a);
        b = getv(b);
        if (a == b)
            return 0;
        p[a] = b;
        return 1;
    }
};
vector<array<int, 4>> bb;
vector<int> banned;
vector<int> inba(int n) {
    dsu usd(n);
    vector<int> vec;
    for (int i = 0; i < bb.size(); ++i) {
        if (!banned[i] and usd.merge(bb[i][0], bb[i][1])) {
            vec.push_back(i);

        }
    }
    return vec;
}
vector<int> getel(int n, vector<int> ind) {
    dsu usd(n);
    vector<int> vec;
    for (auto i : ind) {
        if (usd.merge(bb[i][0], bb[i][1])) {
            vec.push_back(i);
        }
    }
    return vec;
}
bool chk(int n, int v, vector<int> indexes) {
    dsu usd(n);
    int rb = 1;
    for (auto i : indexes) {
        if (v != i)
            rb += usd.merge(bb[i][0], bb[i][1]);
        if (rb == n)
            return 1;
    }
    return 0;
}
int cococo(vector<int> r) {
    for (auto &i : r)
        i = bb[i][3];
    return count_common_roads(r);
}
int countpls1(vector<int> r, int a) {
    r.push_back(a);
    return cococo(r);
}
int weightedask(vector<int> a) {
    //cout << "DD" << endl;
    int res = 0;
    for (auto i : a) {
        if (bb[i][2] != -1)
            res -= bb[i][2];
    }
    int vl = res + cococo(a);
    //cout << "EE" << endl;
    return vl;
}
int cmp(int n, int a, int b, vector<int> indexes) {
    dsu usd(n);
    int vv;
    if (bb[a][0] == bb[b][0] or bb[a][0] == bb[b][1]) {
        vv = bb[a][0];
    } else {
        vv = bb[a][1];
    }
    int nva = bb[a][0] + bb[a][1] - vv;
    int nvb = bb[b][0] + bb[b][1] - vv;
    int rb = 1;
    vector<int> tocmp;
    //cout << rb << ' ' << a << ' ' << b << endl;
    for (auto i : indexes) {
        //cout << i << endl;
        if (bb[i][0] != vv and bb[i][1] != vv and usd.merge(bb[i][0], bb[i][1])) {
            rb += 1;
            tocmp.push_back(i);
        }
    }
    for (auto i : indexes) {
        //cout << i << endl;
        if (bb[i][0] == vv or bb[i][1] == vv) {
            int vt = bb[i][0] + bb[i][1] - vv;
            if (usd.getv(vt) != usd.getv(nva) and usd.getv(vt) != usd.getv(nvb) and usd.merge(vv, vt)) {
                rb += 1;
                tocmp.push_back(i);
            }
        }
    }
    if (rb != n - 1)
        return -10;
    //cout << vv << endl;
    //cout << a << endl;
    int vl1 = countpls1(tocmp, a);
    int vl2 = countpls1(tocmp, b);
    // cout << a << ' ' << vl1 << ' ' << b << ' ' << vl2 << endl;
    return vl2 - vl1;
}
struct dsutype {
    vector<int> p;
    vector<int> tp;
    dsutype(int n, vector<int> tps) {
        p.assign(n, {});
        tp = tps;
        for (int i = 0; i < n; ++i) {
            p[i] = i;
        }
    }
    int getv(int v) {
        if (p[v] == v)
            return v;
        return p[v] = getv(p[v]);
    }
    bool merge(int n, int a, int b, vector<int> &indexes) {
        int aorig = a, borig = b;
        a = getv(a);
        b = getv(b);
        if (tp[a] == -1 or tp[b] == -1) {
            int quer = cmp(n, aorig, borig, indexes);
            if (quer == -10)
                return 0;
            int vl = max(tp[a], tp[b]);
            if (quer == 0) {
                p[b] = a;
                tp[a] = vl;
            }
            if (quer == 1) {
                tp[b] = 1;
                tp[a] = 0;
            }
            if (quer == -1) {
                tp[b] = 0;
                tp[a] = 1;
            }
            return 1;
        }
        return 0;
    }
};
int zprsmart(int n, vector<int> addp, vector<int> knw) {
    if (addp.empty())
        return 0;
    //cout << "ZPSt\n";
    dsu usd(n);
    vector<int> tocmp;
    for (auto i : addp) {
        tocmp.push_back(i);
        if (!usd.merge(bb[i][0], bb[i][1]))
            while (1);
    }
    for (auto i : knw) {
        if (usd.merge(bb[i][0], bb[i][1]))
            tocmp.push_back(i);
    }
    int vl = weightedask(tocmp);
    //cout << "ZPend\n";
    return vl;
}
std::vector<int> find_roads(int n, vector<int> u, vector<int> v) {
    bb.assign(u.size(), {});
    for (int i = 0; i < u.size(); ++i) {
        bb[i] = {u[i], v[i], -1, i};
    }
    for (int i = 0; i < bb.size(); ++i) {
      //  swap(bb[i], bb[rand() % bb.size()]);
    }
    banned.assign(u.size(), 0);
    /*vector<int> maybe(u.size());
    for (int i = 0; i < u.size(); ++i) {
        maybe[i] = i;
    }*/
    vector<int> maybe = inba(n);
    for (auto i : maybe)
        banned[i] = 1;
    for (int i = 0; i < 1; ++i) {
        vector<int> maybe2 = inba(n);
        for (auto i : maybe2) {
            //cerr << i << endl;
            maybe.push_back(i);
        }
    }

    vector<int> tpp(u.size(), -1);
    for (auto i : maybe) {
        if (!chk(n, i, maybe)) {
            bb[i][2] = 1;
            tpp[i] = 1;
        }
    }
    dsutype usd(tpp.size(), tpp);
    int cc = 0;
    for (auto i : maybe) {
        for (auto j : maybe) {
            if (i == j)
                break;
            if (bb[i][0] == bb[j][0] or bb[i][0] == bb[j][1] or bb[i][1] == bb[j][0] or bb[i][1] == bb[j][1]) {
                //cout << i << ' ' << j << endl;
                usd.merge(n, i, j, maybe);
            }
        }
        cc++;
    }
    vector<int> knowres2, knowres;
    for (auto i : maybe) {
        if (usd.getv(i) != i and usd.tp[usd.getv(i)] == -1) {
            usd.tp[usd.getv(i)] = 0;
        }
    }
    for (auto i : maybe) {
        if (usd.tp[usd.getv(i)] != -1) {
            bb[i][2] = usd.tp[usd.getv(i)];
            knowres2.push_back(i);
        }
    }
    knowres = getel(n, knowres2);
    if (knowres.size() != n - 1)
        while (1);
    vector<vector<int>> g(n);
    for (int i = 0; i < v.size(); ++i) {
        g[bb[i][0]].push_back(i);
        g[bb[i][1]].push_back(i);
    }
    for (int i = 0; i < n; ++i) {
        vector<int> clred;
        for (auto j : g[i]) {
            if (bb[j][2] == -1)
                clred.push_back(j);
        }
        int fr = -1;
        while (fr != clred.size()) {
            int l = fr, r = clred.size();
            bool ok = 1;
            for (int j = 128; j >= 1; j /= 2) {
                int m = fr + j;
                if (m > r)
                    continue;
                vector<int> tepa;
                for (int j = fr+1; j < m; ++j) {
                    tepa.push_back(clred[j]);
                }
                if (!zprsmart(n, tepa, knowres)) {
                    fr = m;
                    if (j == 128) {
                        ok = 0;
                        break;
                    }
                }
            }
            if (ok) {
                if (fr != clred.size()) {
                    bb[clred[fr]][2] = 1;
                }
            }
        }
        for (auto j : clred) {
            if (bb[j][2] == -1)
                bb[j][2] = 0;
        }
    }
    //cout << "DAAA" << endl;
    vector<int> resba;
    for (int i = 0; i < bb.size(); ++i) {
        if (bb[i][2] == 1)
            resba.push_back(bb[i][3]);
    }
    return resba;
}


/*
static int MAXQ = 30000;

static int n, m, q = 0;
static vector<int> u, v;
static vector<bool> goal;

static void wrong_answer() {
    printf("NO\n");
    exit(0);
}

static bool is_valid(const vector<int>& r) {
    if(int(r.size()) != n - 1)
        return false;

    for(int i = 0; i < n - 1; i++)
        if (r[i] < 0 || r[i] >= m)
            return false;

    return true;
}

static int _count_common_roads_internal(const vector<int>& r) {
    dsu usd(n);
    if(!is_valid(r)) {
        cout << "invalid query\n";
        for (auto i : r)
            cout << i << ' ';
        cout << endl;
        wrong_answer();
    }
    int rb = 1;
    for (auto i : r) {
        rb += usd.merge(u[i], v[i]);
    }
    if (rb != n) {
        cout << "invalid query\n";
        for (auto i : r)
            cout << i << ' ';
        cout << endl;
        wrong_answer();
    }
    int common = 0;
    for(int i = 0; i < n - 1; i++) {
        bool is_common = goal[r[i]];
        if (is_common)
            common++;
    }

    return common;
}

int count_common_roads(const vector<int>& r) {
    q++;
    if(q > MAXQ)
        wrong_answer();

    return _count_common_roads_internal(r);
}

int main() {
    assert(2 == scanf("%d %d", &n, &m));

    u.resize(m);
    v.resize(m);

    for(int i = 0; i < m; i++)
        assert(2 == scanf("%d %d", &u[i], &v[i]));

    goal.resize(m, false);

    for(int i = 0; i < n - 1; i++) {
        int id;
        assert(1 == scanf("%d", &id));
        goal[id] = true;
    }

    vector<int> res = find_roads(n, u, v);

    if(_count_common_roads_internal(res) != n - 1)
        wrong_answer();

    printf("YES\n");

    return 0;
}
*/
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 13
Accepted
time: 0ms
memory: 3748kb

input:

wrslcnopzlckvxbnair_input_simurgh_lmncvpisadngpiqdfngslcnvd
7 21 30000
2 0
0 1
5 2
2 6
1 3
3 0
6 0
4 5
3 2
4 0
1 4
0 5
4 3
4 6
6 1
2 1
5 3
2 4
5 6
5 1
6 3
7 10 9 13 12 17

output:

lxndanfdiadsfnslkj_output_simurgh_faifnbsidjvnsidjbgsidjgbs
OK
7 9 10 12 13 17

result:

ok correct

Test #2:

score: -13
Wrong Answer
time: 0ms
memory: 3736kb

input:

wrslcnopzlckvxbnair_input_simurgh_lmncvpisadngpiqdfngslcnvd
7 21 30000
4 6
1 6
2 3
0 3
2 1
2 6
5 6
6 3
0 2
1 0
4 2
1 3
5 2
5 0
0 6
5 3
4 5
5 1
3 4
1 4
4 0
4 16 10 0 20 18

output:

lxndanfdiadsfnslkj_output_simurgh_faifnbsidjvnsidjbgsidjgbs
WA
NO

result:

wrong answer WA in grader: NO

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #58:

score: 19
Accepted
time: 0ms
memory: 3812kb

input:

wrslcnopzlckvxbnair_input_simurgh_lmncvpisadngpiqdfngslcnvd
2 1 12000
1 0
0

output:

lxndanfdiadsfnslkj_output_simurgh_faifnbsidjvnsidjbgsidjgbs
OK
0

result:

ok correct

Test #59:

score: -19
Wrong Answer
time: 0ms
memory: 3800kb

input:

wrslcnopzlckvxbnair_input_simurgh_lmncvpisadngpiqdfngslcnvd
10 45 12000
4 8
0 5
2 0
5 8
8 0
3 8
6 4
4 1
2 3
2 1
6 2
1 7
3 7
8 1
7 0
8 6
0 6
9 5
9 6
7 4
7 6
7 9
1 6
3 5
2 5
7 5
3 9
0 3
3 6
2 9
1 5
0 4
7 8
5 4
9 4
5 6
3 1
2 8
7 2
2 4
1 0
9 8
4 3
1 9
9 0
22 41 3 16 7 25 28 11 39

output:

lxndanfdiadsfnslkj_output_simurgh_faifnbsidjvnsidjbgsidjgbs
WA
NO

result:

wrong answer WA in grader: NO

Subtask #5:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

Server Time: 2024-11-29 23:39:12 | OpenSource Project