Submission #237514

# Submission time Handle Problem Language Result Execution time Memory
237514 2020-06-07T06:56:59 Z IgorI Friends (BOI17_friends) C++17
0 / 100
5 ms 1536 KB
const int LG = 21;
const int FN = 400005;
const long long MOD = 1e9 + 7;
const long long INF = 1e9;
const long long INFLL = 1e18;

#include <bits/stdc++.h>

using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define fi first
#define se second
#define re return
#define pb push_back
#define uniq(x) sort(all(x)); (x).resize(unique(all(x)) - (x).begin())

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
#define ln cerr << __LINE__ << endl
#else
#define dbg(x) void(0)
#define ln void(0)
#endif // LOCAL

vector<vector<int> > ans;
int n, p, q;
vector<int> g[5000];
int a[50000];
int b[50000];
vector<int> graph[5000];
int c[3000][3000];
int color[3000];
int in[3000];
int up[3000];
int T = 1;
int marker;

int sz[3000];
int ok[3000];
int success;

bool no(vector<int> &v, int x)
{
    forn(i, v.size()) if (v[i] == x) return 0;
    return 1;
}

int dfs(int v, int par, int End, int Start)
{
    if (!success) return 0;
    sz[v] = 1;
    in[v] = up[v] = T++;
    for (auto e : graph[v])
    {
        int u = a[e] + b[e] - v;
        if (u == par) continue;
        if (in[u] == 0)
        {
            if (v == End && u == Start) continue;
            dfs(u, v, End, Start);
            sz[v] += sz[u];
        }
        up[v] = min(up[v], up[u]);
    }
    if (up[v] == in[v])
    {
        //this node is top
        vector<int> q = {v};
        vector<int> down_sizes;
        for (int i = 0; i < q.size(); i++)
        {
            for (auto id : graph[q[i]])
            {
                int u = a[id] + b[id] - q[i];
                if (u == par) continue;
                int t = 0;
                for (int j = 0; j < q.size(); j++) if (q[j] == u) t = 1;
                if (t == 1) continue;
                if (ok[u])
                {
                    down_sizes.push_back(sz[u]);
                }
                else
                {
                    q.push_back(u);
                }
            }
            if (q.size() > 15)
            {
                success = 0;
                return 0;
            }
        }
        if (down_sizes.size() == 0)
        {
            int fl = 0;
            for (int i = 0; i < q.size(); i++) if (q[i] == End) fl = 1;
            if (q.size() <= p && fl)
            {
                ok[v] = 1;
                return 1;
            }
            else
            {
                if (q.size() >= p)
                {
                    success = 0;
                    return 0;
                }
                else
                {
                    return 1;
                }
            }
        }
        if (down_sizes.size() == 1)
        {
            int our = sz[v] - down_sizes[0];
            if (our <= p)
            {
                ok[v] = 1;
                return 1;
            }
            else
            {
                success = 0;
                return 0;
            }
        }
        exit(1);
    }
    return success;
}

void opa(int v)
{
    marker++;
    vector<int> q = {v};
    color[v] = marker;
    vector<int> ids;
    for (int i = 0; i < q.size(); i++)
    {
        for (int j = 0; j < graph[q[i]].size(); j++)
        {
            int u = a[graph[q[i]][j]] + b[graph[q[i]][j]] - q[i];
            if (color[u] == 0)
            {
                color[u] = marker;
                ids.push_back(graph[q[i]][j]);
                q.push_back(u);
            }
        }
    }
    if (q.size() <= p)
        return;
    for (int i = 0; i < ids.size(); i++)
    {
        success = 1;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> p >> q;
    for (int i = 0; i < n; i++)
    {
        int k;
        cin >> k;
        g[i].resize(k);
        for (int j = 0; j < k; j++)
        {
            cin >> g[i][j];
            c[i][g[i][j]] = 1;
        }
    }
    int f = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (c[i][j] + c[j][i] == 1)
            {
                cout << "detention";
                return 0;
            }
            if (c[i][j])
            {
                graph[i].push_back(f);
                graph[j].push_back(f);
                a[f] = i;
                b[f] = j;
                f++;
            }
        }
    }
    if (q == 0)
    {
        //each component size <= p
        vector<vector<int> > ans;
        for (int i = 0; i < n; i++)
        {
            if (color[i] == 0)
            {
                vector<int> s = {i};
                color[i] = 1;
                for (int j = 0; j < s.size(); j++)
                {
                    for (auto id : graph[s[j]])
                    {
                        int u = a[id] + b[id] - s[j];
                        if (color[u] == 0)
                        {
                            color[u] = 1;
                            s.push_back(u);
                        }
                    }
                }
                if (s.size() > p)
                {
                    cout << "detention";
                    return 0;
                }
                ans.push_back(s);
            }
        }
        cout << "home\n";
        forn(i, ans.size())
        {
            cout << ans[i].size() << " ";
            forn(j, ans[i].size())
            {
                cout << ans[i][j] << " ";
            }
            cout << "\n";
        }
        return 0;
    }
    if (q == 1)
    {
        //each component can be splitted in two with sizes <= p
        vector<vector<int> > ans;
        for (int i = 0; i < n; i++)
        {
            if (color[i] == 0)
            {
                vector<int> s = {i};
                color[i] = 1;
                vector<int> ids;
                for (int j = 0; j < s.size(); j++)
                {
                    for (auto id : graph[s[j]])
                    {
                        int u = a[id] + b[id] - s[j];
                        if (color[u] == 0)
                        {
                            color[u] = 1;
                            s.push_back(u);
                            ids.push_back(id);
                        }
                    }
                }
                if (s.size() > 2 * p)
                {
                    cout << "detention";
                    return 0;
                }
                if (s.size() <= p)
                {
                    ans.push_back(s);
                    continue;
                }
                int fl = 0;
                for (auto e : ids)
                {
                    int v1 = a[e], v2 = b[e];
                    vector<int> r = {v2, v1}, s = {v1, v2};
                    for (int i = 1; i < r.size(); i++)
                    {
                        for (auto id : graph[r[i]])
                        {
                            int u = a[id] + b[id] - r[i];
                            if (no(r, u))
                            {
                                r.push_back(u);
                            }
                        }
                    }
                    for (int i = 1; i < s.size(); i++)
                    {
                        for (auto id : graph[s[i]])
                        {
                            int u = a[id] + b[id] - s[i];
                            if (no(s, u))
                            {
                                s.push_back(u);
                            }
                        }
                    }
                    reverse(all(r));
                    reverse(all(s));
                    r.pop_back();
                    s.pop_back();
                    if (r.size() <= p && s.size() <= p)
                    {
                        ans.push_back(r);
                        ans.push_back(s);
                        fl = 1;
                        break;
                    }
                }
                if (!fl)
                {
                    cout << "detention\n";
                    return 0;
                }
            }
        }
        cout << "home\n";
        cout << ans.size() << "\n";
        forn(i, ans.size())
        {
            cout << ans[i].size() << " ";
            forn(j, ans[i].size())
            {
                cout << ans[i][j] << " ";
            }
            cout << "\n";
        }
        return 0;
    }
    for (int i = 0; i < n; i++)
    {
        if (color[i] == 0)
        {
            opa(i);
        }
    }
}

/* Note:
Check constants at the beginning of the code.
    N is set to 4e5 but be careful in problems with large constant factor.
    Setting N in every problem is more effective.
Check corner cases.
    N = 1
No def int long long for now.
Add something here.
*/

Compilation message

friends.cpp: In function 'bool no(std::vector<long long int>&, long long int)':
friends.cpp:17:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
                                      ~~~~^~~~~~
friends.cpp:55:5: note: in expansion of macro 'forn'
     forn(i, v.size()) if (v[i] == x) return 0;
     ^~~~
friends.cpp: In function 'long long int dfs(long long int, long long int, long long int, long long int)':
friends.cpp:81:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < q.size(); i++)
                         ~~^~~~~~~~~~
friends.cpp:88:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = 0; j < q.size(); j++) if (q[j] == u) t = 1;
                                 ~~^~~~~~~~~~
friends.cpp:108:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < q.size(); i++) if (q[i] == End) fl = 1;
                             ~~^~~~~~~~~~
friends.cpp:109:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (q.size() <= p && fl)
                 ~~~~~~~~~^~~~
friends.cpp:116:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (q.size() >= p)
                     ~~~~~~~~~^~~~
friends.cpp: In function 'void opa(long long int)':
friends.cpp:152:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < q.size(); i++)
                     ~~^~~~~~~~~~
friends.cpp:154:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < graph[q[i]].size(); j++)
                         ~~^~~~~~~~~~~~~~~~~~~~
friends.cpp:165:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (q.size() <= p)
         ~~~~~~~~~^~~~
friends.cpp:167:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < ids.size(); i++)
                     ~~^~~~~~~~~~~~
friends.cpp: In function 'int main()':
friends.cpp:220:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = 0; j < s.size(); j++)
                                 ~~^~~~~~~~~~
friends.cpp:232:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (s.size() > p)
                     ~~~~~~~~~^~~
friends.cpp:17:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
                                      ~~~~^~~~~~
friends.cpp:241:9: note: in expansion of macro 'forn'
         forn(i, ans.size())
         ^~~~
friends.cpp:17:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
                                      ~~~~^~~~~~
friends.cpp:244:13: note: in expansion of macro 'forn'
             forn(j, ans[i].size())
             ^~~~
friends.cpp:263:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = 0; j < s.size(); j++)
                                 ~~^~~~~~~~~~
friends.cpp:276:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (s.size() > 2 * p)
                     ~~~~~~~~~^~~~~~~
friends.cpp:281:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (s.size() <= p)
                     ~~~~~~~~~^~~~
friends.cpp:291:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int i = 1; i < r.size(); i++)
                                     ~~^~~~~~~~~~
friends.cpp:302:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int i = 1; i < s.size(); i++)
                                     ~~^~~~~~~~~~
friends.cpp:317:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if (r.size() <= p && s.size() <= p)
                         ~~~~~~~~~^~~~
friends.cpp:317:51: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if (r.size() <= p && s.size() <= p)
                                          ~~~~~~~~~^~~~
friends.cpp:17:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
                                      ~~~~^~~~~~
friends.cpp:334:9: note: in expansion of macro 'forn'
         forn(i, ans.size())
         ^~~~
friends.cpp:17:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
                                      ~~~~^~~~~~
friends.cpp:337:13: note: in expansion of macro 'forn'
             forn(j, ans[i].size())
             ^~~~
# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Incorrect 5 ms 640 KB Unexpected end of file - token expected
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Incorrect 5 ms 1536 KB Unexpected end of file - token expected
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Incorrect 5 ms 1536 KB Unexpected end of file - token expected
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Incorrect 5 ms 640 KB Unexpected end of file - token expected
3 Halted 0 ms 0 KB -