QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#128448	#2760. Simurgh	somethingnew^#	0	0ms	3812kb	C++20	8.5kb	2023-07-21 05:23:09	2024-07-04 00:50:00

Judging History

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

[2024-07-04 00:50:00]
评测

测评结果：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 05:23:09]
提交

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, 3>> 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 countpls1(vector<int> r, int a) {
    r.push_back(a);
    return count_common_roads(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 + count_common_roads(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 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);
        }
    }
    if (rb != n - 1)
        return -10;
    //cout << vv << endl;
    //cout << a << endl;
    int vl1 = countpls1(tocmp, a);
    //cout << b << endl;
    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 vl = max(tp[a], tp[b]);
            int quer = cmp(n, aorig, borig, indexes);
            if (quer == -10)
                return 0;
            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) {
    //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]))
            exit(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};
    }
    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;
    vector<int> maybe2 = inba(n);
    for (auto i : maybe2) {
        //cerr << i << endl;
        maybe.push_back(i);
    }

    vector<int> tpp;
    for (auto i : maybe) {
        if (!chk(n, i, maybe)) {
            bb[i][2] = 1;
            tpp.push_back(1);
        } else {
            tpp.push_back(-1);
        }
    }
    dsutype usd(tpp.size(), tpp);
    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);
            }
        }
    }
    vector<int> knowres2, knowres;
    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)
        exit(2);
    vector<vector<int>> g(n);
    for (int i = 0; i < v.size(); ++i) {
        g[v[i]].push_back(i);
        g[u[i]].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();
            while (l + 1 < r) {
                int m = l + r >> 1;
                vector<int> tepa;
                for (int j = fr+1; j <= m; ++j) {
                    tepa.push_back(clred[j]);
                }
                if (zprsmart(n, tepa, knowres)) {
                    r = m;
                } else {
                    l = m;
                }
            }
            fr = r;
            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(i);
    }
    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: 3812kb

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: 3796kb

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:

Subtask #3:

score: 0

Skipped

Dependency #2:

Subtask #4:

score: 0

Runtime Error

Test #58:

score: 19

Accepted

time: 0ms

memory: 3788kb

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

Runtime Error

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:

Unauthorized output

QOJ.ac

QOJ

Judging History

answer

Details

Subtask #1:

Test #1:

input:

output:

result:

Test #2:

input:

output:

result:

Subtask #2:

Dependency #1:

Subtask #3:

Dependency #2:

Subtask #4:

Test #58:

input:

output:

result:

Test #59:

input:

output:

result:

Subtask #5:

Dependency #1: