oj.uz

Submission #317519

# Submission time Handle Problem Language Result Execution time Memory
317519 2020-10-30T01:08:08 Z mohamedsobhi777 Parachute rings (IOI12_rings) C++14
20 / 100
 4000 ms 183484 KB 
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:10000000")

using namespace std;
int N;
const int cn = 2e6;

vector<int> adj[cn];
int deg[cn];
int vis[cn];
int c;
bool bd = 1;
int del;
vector<int> vec;
vector<int> th;
int asy = 1;
int ac = 0;
int cs = 0;
map<pair<int, int>, int> mp, bad;

struct dsu
{
        int fat[cn];
        dsu()
        {
                memset(fat, 0, sizeof fat);
                for (int i = 0; i < cn; ++i)
                        fat[i] = i;
        }
        inline int find(int x) { return fat[x] = (x == fat[x] ? x : find(fat[x])); }
        inline bool same(int x, int y) { return find(x) == find(y); }
        void link(int u, int v)
        {
                u = find(u);
                v = find(v);
                if (fat[u] != v)
                        fat[u] = v;
        }
} d1;

void dfs(int x, int p)
{
        vis[x] = c;
        int ch = (p != x);

        for (auto u : adj[x])
        {
                if (u == p || del == u)
                        continue;
                if (vis[u] == c)
                        bd = 0;
                else
                        dfs(u, x), ++ch;
        }
        if (ch > 2)
                bd = 0;
}
vector<int> bigs;
vector<int> cyc;
vector<int> now;
int onc[cn];
int prv[cn];
set<int> unic;

bool check(int i)
{
        del = i;
        bool ok = 1;
        ++c;
        dsu cd;
        map<pair<int, int>, int> alr;
        for (auto u : cyc)
        {
                if (u == i)
                        continue;
                for (auto v : adj[u])
                {
                        if (v == i || alr[{u, v}] || alr[{v, u}])
                                continue;
                        if (cd.same(u, v))
                                ok = 0;
                        cd.link(u, v);
                        alr[{u, v}] = 1;
                }
        }
        return ok;
}
int k = 1e3;
int viz[cn];
int tar;
void detect(int x, int p)
{
        memset(prv, -1, sizeof prv);
        ++c;
        queue<int> qu;
        qu.push(x);
        bool add = 1;
        while (qu.size())
        {
                int a = qu.front();
                qu.pop();
                if (a == tar)
                {
                        int cur = tar;
                        while (~cur)
                        {
                                cyc.push_back(cur);
                                if (onc[cur])
                                        add = 0;
                                onc[cur]++;
                                unic.insert(cur);
                                cur = prv[cur];
                        }
                }
                vis[a] = c;
                for (auto u : adj[a])
                {
                        if (u != prv[a] && !bad[{u, a}])
                        {
                                prv[u] = a;
                                qu.push(u);
                        }
                }
        }
        cs += add;
}
int dp3 = -1;
set<int> bbarn;
set<int> cyc3 ; 

int brute()
{
        int ret = 0;
        set<int> uni;
        if (bigs.size() > 1)
                return 0;
        if (cs > 1)
                return 0;
        if (bigs.size())
        {
                int cnt = 0;
                return cnt + 1 >= bbarn.size() && (cs == 0 || onc[bigs[0]]) && bigs.size() == 1;
        }

        if (th.size() > 2)
        {
                int a = th[0];
                int b = th[1];
                int c = th[2];
                if (th.size() == 3 && !cs)
                {

                        assert(a != b && a != c && b != c);
                        int cnt = 0;
                        if (mp[{a, b}] && mp[{a, c}] && (cs == 0 || onc[a]))
                                ++cnt;
                        if (mp[{b, a}] && mp[{b, c}] && (cs == 0 || onc[b]))
                                ++cnt;
                        if (mp[{c, a}] && mp[{c, b}] && (cs == 0 || onc[c]))
                                ++cnt;
                        return cnt;
                }
                else if (th.size() == 3 && cs)
                {
                        int cnt = mp[{a, b}] + mp[{b, c}] + mp[{a, c}];
                        if (~dp3)
                                return dp3;
                        for (auto u : th)
                        {
                                int cn = 0;
                                for (auto j : th)
                                        if (j != u)
                                                cn += mp[{j, u}];
                                if (onc[u])
                                        if (cn == 2 && check(u))
                                        {
                                                ++ret;

                                                //  assert(onc[u] && cnt == 3);
                                        }
                                        else
                                        {
                                        }
                        }
                        return dp3 = ret;
                }
                else if (th.size() > 3)
                        return 0;
        }

        if (th.size() == 0 && cs == 0)
                return N;
        if (cs == 1 && th.size() == 0)
        {
                return (int)unic.size();
        }

        int ans1 = 0;
        if (th.size() == 1)
        {
                if (asy)
                        return 1 + (int)adj[*th.begin()].size();
                ++c;
                int a = *th.begin();
                if (cs == 1)
                {
                        ans1 = onc[a];
                        for (auto u : adj[a])
                                ans1 += onc[u];
                        return ans1;
                }
        }
        else if (th.size() == 2)
        {
                int a = th[0];
                int b = th[1];
                if (cs)
                {
                        if (onc[a] + onc[b] == 0)
                                return 0;
                }
                unordered_map<int, int> mp;
                for (auto u : adj[a])
                        mp[u]++;
                for (auto u : adj[b])
                        mp[u]++;
                mp[a]++;
                mp[b]++;
                for (auto u : mp)
                {
                        if ((onc[u.first] || !cs) && u.second == 2)
                                ++ret;
                }
                return ret;
        }
        return 0;
}

void Init(int N_)
{

        N = N_;
}
void Link(int A, int B)
{
        mp[{A, B}] = mp[{B, A}] = 1;

        if (d1.same(A, B))
        {
                ++c;
                ++ac;
                tar = B;
                detect(A, A);
                asy = 0;
                bad[{A, B}] = bad[{B, A}] = 1;
        }
        adj[A].push_back(B);
        adj[B].push_back(A);

        d1.link(A, B);
        deg[A]++;
        deg[B]++;
        if (deg[A] == 4)
        {
                bigs.push_back(A);
                for (auto u : adj[A])
                {
                        if (deg[u] > 2)
                                bbarn.insert(u);
                }
        }
        if (deg[B] == 4)
        {
                bigs.push_back(B);
                for (auto u : adj[B])
                {
                        if (deg[u] > 2)
                                bbarn.insert(u);
                }
        }
        if (deg[A] == 3)
        {
                th.push_back(A);
                if (bigs.size() && mp[{A, bigs[0]}])
                {
                        bbarn.insert(A);
                }
        }
        if (deg[B] == 3)
        {
                th.push_back(B);
                if (bigs.size() && mp[{B, bigs[0]}])
                {
                        bbarn.insert(B);
                }
        }
}

int CountCritical()
{
        if (bigs.size() > 1)
                return 0;
        return brute();
        return N;
}

Compilation message

rings.cpp:2: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    2 | #pragma comment(linker, "/STACK:10000000")
      | 
rings.cpp: In function 'int brute()':
rings.cpp:142:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |                 return cnt + 1 >= bbarn.size() && (cs == 0 || onc[bigs[0]]) && bigs.size() == 1;
      |                        ~~~~~~~~^~~~~~~~~~~~~~~
rings.cpp:174:36: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
  174 |                                 if (onc[u])
      |                                    ^
rings.cpp:165:29: warning: unused variable 'cnt' [-Wunused-variable]
  165 |                         int cnt = mp[{a, b}] + mp[{b, c}] + mp[{a, c}];
      |                             ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 55168 KB Output is correct
2 Correct 44 ms 55804 KB Output is correct
3 Correct 46 ms 55936 KB Output is correct
4 Correct 45 ms 63096 KB Output is correct
5 Correct 48 ms 63740 KB Output is correct
6 Correct 52 ms 64248 KB Output is correct
7 Correct 40 ms 55288 KB Output is correct
8 Correct 61 ms 64120 KB Output is correct
9 Correct 46 ms 56064 KB Output is correct
10 Correct 48 ms 56056 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2035 ms 138764 KB Output is correct
2 Correct 3425 ms 183484 KB Output is correct
3 Execution timed out 4051 ms 170720 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 55168 KB Output is correct
2 Correct 44 ms 55804 KB Output is correct
3 Correct 46 ms 55936 KB Output is correct
4 Correct 45 ms 63096 KB Output is correct
5 Correct 48 ms 63740 KB Output is correct
6 Correct 52 ms 64248 KB Output is correct
7 Correct 40 ms 55288 KB Output is correct
8 Correct 61 ms 64120 KB Output is correct
9 Correct 46 ms 56064 KB Output is correct
10 Correct 48 ms 56056 KB Output is correct
11 Correct 83 ms 72056 KB Output is correct
12 Correct 718 ms 66972 KB Output is correct
13 Incorrect 1775 ms 75520 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 55168 KB Output is correct
2 Correct 44 ms 55804 KB Output is correct
3 Correct 46 ms 55936 KB Output is correct
4 Correct 45 ms 63096 KB Output is correct
5 Correct 48 ms 63740 KB Output is correct
6 Correct 52 ms 64248 KB Output is correct
7 Correct 40 ms 55288 KB Output is correct
8 Correct 61 ms 64120 KB Output is correct
9 Correct 46 ms 56064 KB Output is correct
10 Correct 48 ms 56056 KB Output is correct
11 Correct 83 ms 72056 KB Output is correct
12 Correct 718 ms 66972 KB Output is correct
13 Incorrect 1775 ms 75520 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 55168 KB Output is correct
2 Correct 44 ms 55804 KB Output is correct
3 Correct 46 ms 55936 KB Output is correct
4 Correct 45 ms 63096 KB Output is correct
5 Correct 48 ms 63740 KB Output is correct
6 Correct 52 ms 64248 KB Output is correct
7 Correct 40 ms 55288 KB Output is correct
8 Correct 61 ms 64120 KB Output is correct
9 Correct 46 ms 56064 KB Output is correct
10 Correct 48 ms 56056 KB Output is correct
11 Correct 2035 ms 138764 KB Output is correct
12 Correct 3425 ms 183484 KB Output is correct
13 Execution timed out 4051 ms 170720 KB Time limit exceeded
14 Halted 0 ms 0 KB -