Submission #1018258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018258		c2zi6	Split the Attractions (IOI19_split)	C++14	Compilation error	0 ms	0 KiB

split

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "split.h"

namespace TEST1 {
    bool check(int n, int A, int B, int C, VI P, VI Q) {
        int m = P.size();
        VI degree(n);
        rep(i, m) {
            degree[P[i]]++;
            degree[Q[i]]++;
        }
        for (int x : degree) if (x > 2) return false;
        return true;
    }
    VI find_split(int n, int A, int B, int C, VI U, VI V) {
        VVI gp(n);
        int m = U.size();
        rep(i, m) {
            gp[U[i]].pb(V[i]);
            gp[V[i]].pb(U[i]);
        }
        int st = -1;
        int nd = -1;
        rep(u, n) if (gp[u].size() == 1) {
            if (st == -1) st = u;
            else nd = u;
        }
        if (st == -1) {
            st = 0;
            nd = gp[0].back();
            gp[0].pop_back();
        }

        VI ans(n, 3);
        auto color = [&](int u, int cnt, int col) {
            int p = -1;
            while (cnt--) {
                ans[u] = col;
                for (int v : gp[u]) if (v != p) {
                    p = u;
                    u = v;
                    break;
                }
            }
            
        };
        color(st, A, 1);
        color(nd, B, 2);
        return ans;
    }
};
namespace TEST2 {
    int n;
    VVI gp;
    VI vis;
    VI ans;
    int cnt;
    void dfs(int u) {
        if (cnt == 0) return;
        ans[u] = 2;
        cnt--;
        vis[u] = true;
        for (int v : gp[u]) if (!vis[v]) {
            dfs(v);
        }
    }
    VI find_split(int N, int A, int B, int C, VI U, VI V) {
        n = N;
        gp = VVI(n);
        int m = U.size();
        rep(i, m) {
            gp[U[i]].pb(V[i]);
            gp[V[i]].pb(U[i]);
        }
        vis = VI(n);
        ans = VI(n, 3);
        cnt = B;
        dfs(0);
        rep(u, n) if (ans[u] == 3) {
            ans[u] = 1;
            break;
        }
        return ans;
    }
};
namespace TEST3 {
    int n;
    VVI gp;
    VI sub;
    VI par;
    void dfs1(int u = 0, int p = -1) {
        par[u] = p;
        sub[u] = 1;
        for (int v : gp[u]) if (v != p) {
            dfs1(v, u);
            sub[u] += sub[v];
        }
    }
    VI ans;
    int col;
    int cnt;
    void dfs2(int u, int p) {
        if (cnt == 0) return;
        ans[u] = col;
        cnt--;
        for (int v : gp[u]) if (v != p) {
            dfs2(v, u);
        }
    }
    VI find_split(int N, int A, int B, int C, VI U, VI V) {
        // sorting
        map<int, int> real;
        real[1] = 1;
        real[2] = 2;
        real[3] = 3;
        if (A > B) {
            swap(A, B);
            swap(real[1], real[2]);
        }
        if (B > C) {
            swap(B, C);
            swap(real[2], real[3]);
        }
        if (A > B) {
            swap(A, B);
            swap(real[1], real[2]);
        }
        /*cout << A << " " << B << " " << C << endl;*/
        /*cout << "MUST REPLACE " << 1 << " WITH " << real[1] << endl;*/
        /*cout << "MUST REPLACE " << 2 << " WITH " << real[2] << endl;*/
        /*cout << "MUST REPLACE " << 3 << " WITH " << real[3] << endl;*/
        n = N;
        int m = U.size();
        gp = VVI(n);
        rep(i, m) {
            gp[U[i]].pb(V[i]);
            gp[V[i]].pb(U[i]);
        }
        par = sub = VI(n);
        dfs1();
        int st = -1; //B
        int nd = -1; //A
        rep(u, n) {
            if (n-sub[u] >= A && sub[u] >= B) {
                st = u;
                nd = par[u];
                break;
            }
        }
        if (st == -1) return VI(n, 0);
        ans = VI(n, 3);
        col = 1;
        cnt = A;
        dfs2(nd, st);
        col = 2;
        cnt = B;
        dfs2(st, nd);
        for (int& x : ans) x = real[x];
        return ans;
    }
};
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "split.h"

namespace TEST1 {
    bool check(int n, int A, int B, int C, VI P, VI Q) {
        int m = P.size();
        VI degree(n);
        rep(i, m) {
            degree[P[i]]++;
            degree[Q[i]]++;
        }
        for (int x : degree) if (x > 2) return false;
        return true;
    }
    VI find_split(int n, int A, int B, int C, VI U, VI V) {
        VVI gp(n);
        int m = U.size();
        rep(i, m) {
            gp[U[i]].pb(V[i]);
            gp[V[i]].pb(U[i]);
        }
        int st = -1;
        int nd = -1;
        rep(u, n) if (gp[u].size() == 1) {
            if (st == -1) st = u;
            else nd = u;
        }
        if (st == -1) {
            st = 0;
            nd = gp[0].back();
            gp[0].pop_back();
        }

        VI ans(n, 3);
        auto color = [&](int u, int cnt, int col) {
            int p = -1;
            while (cnt--) {
                ans[u] = col;
                for (int v : gp[u]) if (v != p) {
                    p = u;
                    u = v;
                    break;
                }
            }
            
        };
        color(st, A, 1);
        color(nd, B, 2);
        return ans;
    }
};
namespace TEST2 {
    int n;
    VVI gp;
    VI vis;
    VI ans;
    int cnt;
    void dfs(int u) {
        if (cnt == 0) return;
        ans[u] = 2;
        cnt--;
        vis[u] = true;
        for (int v : gp[u]) if (!vis[v]) {
            dfs(v);
        }
    }
    VI find_split(int N, int A, int B, int C, VI U, VI V) {
        n = N;
        gp = VVI(n);
        int m = U.size();
        rep(i, m) {
            gp[U[i]].pb(V[i]);
            gp[V[i]].pb(U[i]);
        }
        vis = VI(n);
        ans = VI(n, 3);
        cnt = B;
        dfs(0);
        rep(u, n) if (ans[u] == 3) {
            ans[u] = 1;
            break;
        }
        return ans;
    }
};
namespace TEST3 {
    int n;
    VVI gp;
    VI sub;
    VI par;
    void dfs1(int u = 0, int p = -1) {
        par[u] = p;
        sub[u] = 1;
        for (int v : gp[u]) if (v != p) {
            dfs1(v, u);
            sub[u] += sub[v];
        }
    }
    VI ans;
    int col;
    int cnt;
    void dfs2(int u, int p) {
        if (cnt == 0) return;
        ans[u] = col;
        cnt--;
        for (int v : gp[u]) if (v != p) {
            dfs2(v, u);
        }
    }
    VI find_split(int N, int A, int B, int C, VI U, VI V) {
        // sorting
        map<int, int> real;
        real[1] = 1;
        real[2] = 2;
        real[3] = 3;
        if (A > B) {
            swap(A, B);
            swap(real[1], real[2]);
        }
        if (B > C) {
            swap(B, C);
            swap(real[2], real[3]);
        }
        if (A > B) {
            swap(A, B);
            swap(real[1], real[2]);
        }
        /*cout << A << " " << B << " " << C << endl;*/
        /*cout << "MUST REPLACE " << 1 << " WITH " << real[1] << endl;*/
        /*cout << "MUST REPLACE " << 2 << " WITH " << real[2] << endl;*/
        /*cout << "MUST REPLACE " << 3 << " WITH " << real[3] << endl;*/
        n = N;
        int m = U.size();
        gp = VVI(n);
        rep(i, m) {
            gp[U[i]].pb(V[i]);
            gp[V[i]].pb(U[i]);
        }
        par = sub = VI(n);
        dfs1();
        int st = -1; //B
        int nd = -1; //A
        rep(u, n) {
            if (n-sub[u] >= A && sub[u] >= A) {
                if (sub[u] >= n/2) {
                    st = u;
                    nd = par[u];
                } else {
                    st = par[u];
                    nd = u;
                }
                break;
            }
        }
        if (st == -1) return VI(n, 0);
        ans = VI(n, 3);
        col = 1;
        cnt = A;
        dfs2(nd, st);
        col = 2;
        cnt = B;
        dfs2(st, nd);
        for (int& x : ans) x = real[x];
        return ans;
    }
};

VI find_split(int n, int A, int B, int C, VI P, VI Q) {
    if (TEST1::check(n, A, B, C, P, Q)) return TEST1::find_split(n, A, B, C, P, Q);
    if (A == 1) return TEST2::find_split(n, A, B, C, P, Q);
    return TEST3::find_split(n, A, B, C, P, Q);
}

Compilation message (stderr)

split.cpp:217:21: error: redefinition of 'template<class T> T setmax(T&, T)'
  217 | template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
      |                     ^~~~~~
split.cpp:26:21: note: 'template<class T> T setmax(T&, T)' previously declared here
   26 | template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
      |                     ^~~~~~
split.cpp:218:21: error: redefinition of 'template<class T> T setmin(T&, T)'
  218 | template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
      |                     ^~~~~~
split.cpp:27:21: note: 'template<class T> T setmin(T&, T)' previously declared here
   27 | template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
      |                     ^~~~~~
split.cpp:226:10: error: redefinition of 'bool TEST1::check(int, int, int, int, VI, VI)'
  226 |     bool check(int n, int A, int B, int C, VI P, VI Q) {
      |          ^~~~~
split.cpp:35:10: note: 'bool TEST1::check(int, int, int, int, VI, VI)' previously defined here
   35 |     bool check(int n, int A, int B, int C, VI P, VI Q) {
      |          ^~~~~
split.cpp:236:8: error: redefinition of 'VI TEST1::find_split(int, int, int, int, VI, VI)'
  236 |     VI find_split(int n, int A, int B, int C, VI U, VI V) {
      |        ^~~~~~~~~~
split.cpp:45:8: note: 'VI TEST1::find_split(int, int, int, int, VI, VI)' previously defined here
   45 |     VI find_split(int n, int A, int B, int C, VI U, VI V) {
      |        ^~~~~~~~~~
split.cpp:274:9: error: redefinition of 'int TEST2::n'
  274 |     int n;
      |         ^
split.cpp:83:9: note: 'int TEST2::n' previously declared here
   83 |     int n;
      |         ^
split.cpp:275:9: error: redefinition of 'VVI TEST2::gp'
  275 |     VVI gp;
      |         ^~
split.cpp:84:9: note: 'VVI TEST2::gp' previously declared here
   84 |     VVI gp;
      |         ^~
split.cpp:276:8: error: redefinition of 'VI TEST2::vis'
  276 |     VI vis;
      |        ^~~
split.cpp:85:8: note: 'VI TEST2::vis' previously declared here
   85 |     VI vis;
      |        ^~~
split.cpp:277:8: error: redefinition of 'VI TEST2::ans'
  277 |     VI ans;
      |        ^~~
split.cpp:86:8: note: 'VI TEST2::ans' previously declared here
   86 |     VI ans;
      |        ^~~
split.cpp:278:9: error: redefinition of 'int TEST2::cnt'
  278 |     int cnt;
      |         ^~~
split.cpp:87:9: note: 'int TEST2::cnt' previously declared here
   87 |     int cnt;
      |         ^~~
split.cpp:279:10: error: redefinition of 'void TEST2::dfs(int)'
  279 |     void dfs(int u) {
      |          ^~~
split.cpp:88:10: note: 'void TEST2::dfs(int)' previously defined here
   88 |     void dfs(int u) {
      |          ^~~
split.cpp:288:8: error: redefinition of 'VI TEST2::find_split(int, int, int, int, VI, VI)'
  288 |     VI find_split(int N, int A, int B, int C, VI U, VI V) {
      |        ^~~~~~~~~~
split.cpp:97:8: note: 'VI TEST2::find_split(int, int, int, int, VI, VI)' previously defined here
   97 |     VI find_split(int N, int A, int B, int C, VI U, VI V) {
      |        ^~~~~~~~~~
split.cpp:308:9: error: redefinition of 'int TEST3::n'
  308 |     int n;
      |         ^
split.cpp:117:9: note: 'int TEST3::n' previously declared here
  117 |     int n;
      |         ^
split.cpp:309:9: error: redefinition of 'VVI TEST3::gp'
  309 |     VVI gp;
      |         ^~
split.cpp:118:9: note: 'VVI TEST3::gp' previously declared here
  118 |     VVI gp;
      |         ^~
split.cpp:310:8: error: redefinition of 'VI TEST3::sub'
  310 |     VI sub;
      |        ^~~
split.cpp:119:8: note: 'VI TEST3::sub' previously declared here
  119 |     VI sub;
      |        ^~~
split.cpp:311:8: error: redefinition of 'VI TEST3::par'
  311 |     VI par;
      |        ^~~
split.cpp:120:8: note: 'VI TEST3::par' previously declared here
  120 |     VI par;
      |        ^~~
split.cpp:312:10: error: redefinition of 'void TEST3::dfs1(int, int)'
  312 |     void dfs1(int u = 0, int p = -1) {
      |          ^~~~
split.cpp:121:10: note: 'void TEST3::dfs1(int, int)' previously defined here
  121 |     void dfs1(int u = 0, int p = -1) {
      |          ^~~~
split.cpp:320:8: error: redefinition of 'VI TEST3::ans'
  320 |     VI ans;
      |        ^~~
split.cpp:129:8: note: 'VI TEST3::ans' previously declared here
  129 |     VI ans;
      |        ^~~
split.cpp:321:9: error: redefinition of 'int TEST3::col'
  321 |     int col;
      |         ^~~
split.cpp:130:9: note: 'int TEST3::col' previously declared here
  130 |     int col;
      |         ^~~
split.cpp:322:9: error: redefinition of 'int TEST3::cnt'
  322 |     int cnt;
      |         ^~~
split.cpp:131:9: note: 'int TEST3::cnt' previously declared here
  131 |     int cnt;
      |         ^~~
split.cpp:323:10: error: redefinition of 'void TEST3::dfs2(int, int)'
  323 |     void dfs2(int u, int p) {
      |          ^~~~
split.cpp:132:10: note: 'void TEST3::dfs2(int, int)' previously defined here
  132 |     void dfs2(int u, int p) {
      |          ^~~~
split.cpp:331:8: error: redefinition of 'VI TEST3::find_split(int, int, int, int, VI, VI)'
  331 |     VI find_split(int N, int A, int B, int C, VI U, VI V) {
      |        ^~~~~~~~~~
split.cpp:140:8: note: 'VI TEST3::find_split(int, int, int, int, VI, VI)' previously defined here
  140 |     VI find_split(int N, int A, int B, int C, VI U, VI V) {
      |        ^~~~~~~~~~