QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#152333#141. 8 染色HaccerKat0 30ms21088kbC++209.9kb2023-08-28 03:01:342023-08-28 03:01:35

Judging History

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

  • [2023-08-28 03:01:35]
  • 评测
  • 测评结果：0
  • 用时：30ms
  • 内存：21088kb
查看
  • [2023-08-28 03:01:34]
  • 提交

Alice

#include <bits/stdc++.h>
using namespace std;
template<typename T>
int SIZE(T (&t)){
    return t.size();
}

template<typename T, size_t N>
int SIZE(T (&t)[N]){
    return N;
}

string to_string(char t){
    return "'" + string({t}) + "'";
}

string to_string(bool t){
    return t ? "true" : "false";
}

string to_string(const string &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += t[i];
    }
    return '"' + ret + '"';
}

string to_string(const char* t){
    string ret(t);
    return to_string(ret);
}

template<size_t N>
string to_string(const bitset<N> &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){
        ret += t[i] + '0';
    }
    return to_string(ret);
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C);

template<typename T, typename S>
string to_string(const pair<T, S> &t){
    return "(" + to_string(t.first) + ", " + to_string(t.second) + ")";
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1, int x2, Coords... C){
    string ret = "[";
    x1 = min(x1, SIZE(t));
    auto e = begin(t);
    advance(e,x1);
    for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += to_string(*e, C...) + (i != _i ? ", " : "");
        e = next(e);
    }
    return ret + "]";
}

template<int Index, typename... Ts>
struct print_tuple{
    string operator() (const tuple<Ts...>& t) {
        string ret = print_tuple<Index - 1, Ts...>{}(t);
        ret += (Index ? ", " : "");
        return ret + to_string(get<Index>(t));
    }
};

template<typename... Ts>
struct print_tuple<0, Ts...> {
    string operator() (const tuple<Ts...>& t) {
        return to_string(get<0>(t));
    }
};

template<typename... Ts>
string to_string(const tuple<Ts...>& t) {
    const auto Size = tuple_size<tuple<Ts...>>::value;
    return print_tuple<Size - 1, Ts...>{}(t);
}

void dbgr(){;}
template<typename Heads, typename... Tails>
void dbgr(Heads H, Tails... T){
    cout << to_string(H) << " | ";
    dbgr(T...);
}

void dbgs(){;}
template<typename Heads, typename... Tails>
void dbgs(Heads H, Tails... T){
    cout << H << " ";
    dbgs(T...);
}

/*
formatted functions:
*/

/*
consider __VA_ARGS__ as a whole:
dbgv() prints values only
dbg() prints name and values
*/
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;

#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
//#define dbg(...)

/*
consider __VA_ARGS__ as a sequence of arguments:
dbgr() prints values only
dbgm() prints names and values
*/
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;

#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        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);
    }
};

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
// using u128 = __uint128_t;
// using i128 = __int128;
const int mod = 1000000007;
const int N = 200005;
const int LOG = 20;
const int inf = 1e9;
const double eps = 1e-11;
vector <int> Alice(int N, int M, vector <int> U, vector <int> V, vector <int> C) {
    vector<int> deg(N);
    for (int i = 0; i < M; i++) {
        deg[U[i]]++, deg[V[i]]++;
    }
    
    // dbg(U.size());
    // dbg(V.size());
    // dbg(deg);
    vector<int> X;
    for (int i = 0; i < N; i++) {
        if (deg[i] >= 8) {
            int c = C[i] / 2;
            X.push_back(c & 1);
            X.push_back((c >> 1) & 1);
        }
    }
    
    return X;
}

// int32_t main() {
//     std::ios::sync_with_stdio(false);
//     cin.tie(NULL);
//     // vector<int> X = Alice(10, 14, {2, 3, 2, 6, 3, 4, 8, 7, 2, 0, 4, 1, 3, 4}, 
//     //     {8, 2, 4, 5, 5, 8, 6, 6, 7, 6, 7, 4, 0, 3}, {1, 5, 2, 0, 4, 5, 2, 1, 7, 2});
//     // dbg(X);
// }
Source code, Language: C++20

Bob

#include <bits/stdc++.h>
using namespace std;
template<typename T>
int SIZE(T (&t)){
    return t.size();
}

template<typename T, size_t N>
int SIZE(T (&t)[N]){
    return N;
}

string to_string(char t){
    return "'" + string({t}) + "'";
}

string to_string(bool t){
    return t ? "true" : "false";
}

string to_string(const string &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += t[i];
    }
    return '"' + ret + '"';
}

string to_string(const char* t){
    string ret(t);
    return to_string(ret);
}

template<size_t N>
string to_string(const bitset<N> &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){
        ret += t[i] + '0';
    }
    return to_string(ret);
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C);

template<typename T, typename S>
string to_string(const pair<T, S> &t){
    return "(" + to_string(t.first) + ", " + to_string(t.second) + ")";
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1, int x2, Coords... C){
    string ret = "[";
    x1 = min(x1, SIZE(t));
    auto e = begin(t);
    advance(e,x1);
    for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += to_string(*e, C...) + (i != _i ? ", " : "");
        e = next(e);
    }
    return ret + "]";
}

template<int Index, typename... Ts>
struct print_tuple{
    string operator() (const tuple<Ts...>& t) {
        string ret = print_tuple<Index - 1, Ts...>{}(t);
        ret += (Index ? ", " : "");
        return ret + to_string(get<Index>(t));
    }
};

template<typename... Ts>
struct print_tuple<0, Ts...> {
    string operator() (const tuple<Ts...>& t) {
        return to_string(get<0>(t));
    }
};

template<typename... Ts>
string to_string(const tuple<Ts...>& t) {
    const auto Size = tuple_size<tuple<Ts...>>::value;
    return print_tuple<Size - 1, Ts...>{}(t);
}

void dbgr(){;}
template<typename Heads, typename... Tails>
void dbgr(Heads H, Tails... T){
    cout << to_string(H) << " | ";
    dbgr(T...);
}

void dbgs(){;}
template<typename Heads, typename... Tails>
void dbgs(Heads H, Tails... T){
    cout << H << " ";
    dbgs(T...);
}

/*
formatted functions:
*/

/*
consider __VA_ARGS__ as a whole:
dbgv() prints values only
dbg() prints name and values
*/
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;

#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
//#define dbg(...)

/*
consider __VA_ARGS__ as a sequence of arguments:
dbgr() prints values only
dbgm() prints names and values
*/
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;

#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        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);
    }
};

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
// using u128 = __uint128_t;
// using i128 = __int128;
const int mod = 1000000007;
const int N = 200005;
const int LOG = 20;
const int inf = 1e9;
const double eps = 1e-11;
void dfs(int u, vector<int> &c, vector<vector<int>> &adj) {
    for (int v : adj[u]) {
        if (c[v] == -1) {
            c[v] = c[u] ^ 1;
            dfs(v, c, adj);
        }
    }    
}

vector<int> Bob(int N, int M, vector <int> U, vector <int> V, vector <int> X) {
    int n = X.size();
    vector<int> deg(N), c(N, -1);
    for (int i = 0; i < M; i++) {
        deg[U[i]]++, deg[V[i]]++;
    }
    
    int j = 0;
    for (int i = 0; i < (n >> 1); i++) {
        while (deg[j] < 8) j++;
        c[j] = X[i] + X[i + 1] * 2, j++;
    }
    
    vector<vector<vector<int>>> adj4(4, vector<vector<int>>(N));
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
        int u = U[i], v = V[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
        if (c[u] != -1 && c[v] != -1 && c[u] == c[v]) {
            adj4[c[u]][u].push_back(v);
            adj4[c[v]][v].push_back(u);
        }
    }
    
    vector<vector<int>> cc(4, vector<int>(N));
    vector<int> C(N, -1);
    for (int s = 0; s < 4; s++) {
        cc[s][0] = 0;
        dfs(0, cc[s], adj4[s]);
        for (int i = 0; i < N; i++) {
            if (cc[s][i] != -1) {
                C[i] = s * 2 + cc[s][i];
            }
        }
    }
    
    for (int u = 0; u < N; u++) {
        if (C[u] == -1) {
            vector<bool> used(8);
            for (int v : adj[u]) {
                if (C[v] == -1) continue;
                used[C[v]] = 1;
            }
            
            for (int j = 0; j < 8; j++) {
                if (!used[j]) {
                    C[u] = j;
                    break;
                }
            }
        }
    }
    
    return C;
}

// int32_t main() {
//     std::ios::sync_with_stdio(false);
//     cin.tie(NULL);
// }
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 30ms
memory: 21088kb

input:

10000 500000
5247 482
4774 3796
5245 9386
8794 2818
1911 3240
6925 6008
6313 1737
8668 4913
7892 5444
6740 2271
2100 53
8527 9605
4009 4765
5293 2683
6552 1326
8877 9929
402 9849
8664 6893
1998 7305
155 9477
9753 8036
448 5438
8535 3111
9493 406
7694 2030
5745 6890
5519 3106
8979 5098
9948 2453
5601...

output:

Success
+100000110110000100001010100000100100110001001111000110001000011010001010110000011111101111101011001001010101100011011100110011011010000110011110101010101110100010010111001101111011000101000010010000101011001110101001100011000111101101010111110000110100110110101001000011011101000110010011111...

input:

10000 500000
5247 482
4774 3796
5245 9386
8794 2818
1911 3240
6925 6008
6313 1737
8668 4913
7892 5444
6740 2271
2100 53
8527 9605
4009 4765
5293 2683
6552 1326
8877 9929
402 9849
8664 6893
1998 7305
155 9477
9753 8036
448 5438
8535 3111
9493 406
7694 2030
5745 6890
5519 3106
8979 5098
9948 2453
5601...

output:

Success
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 ...

result:

wrong answer the color of the vertex 5247 and 482 is the same
English 繁體中文 简体中文

Server Time: 2025-01-21 04:58:43 | OpenSource Project