oj.uz

Submission #790239

# Submission time Handle Problem Language Result Execution time Memory
790239 2023-07-22T13:02:27 Z Amylopectin Parachute rings (IOI12_rings) C++14
37 / 100
 931 ms 196960 KB 
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int mxn = 4e6 + 10;
// const int mxn = 110;
vector<int> pat[mxn] = {};
int n,ggr[mxn] = {},see[mxn] = {},deg[mxn] = {},inn[mxn] = {},rus,ruc
,thi[mxn] = {},cyc[mxn] = {},ocy,ret,u[mxn] = {},of;
int figr(int l)
{
  int cn = l,f;
  while(ggr[l] != l)
  {
    l = ggr[l];
  }
  while(ggr[cn] != cn)
  {
    f = ggr[cn];
    ggr[cn] = l;
    cn = f;
  }
  return l;
}
int mer(int l,int r)
{
  int f,cl = figr(l),cr = figr(r);
  if(cl > cr)
  {
    f = cl;
    cl = cr;
    cr = f;
  }
  ggr[cr] = cl;
  // nmem[cl] += nmem[cr];
  return cl;
}
int re(int cn,int be)
{
    int i,j,fn,fou = 0,cva;
    if(cyc[cn] == 1)
    {
        ocy = 1;
        ret = cn;
        return 1;
    }
    u[cn] = 1;
    for(i=0; i<pat[cn].size(); i++)
    {
        fn = pat[cn][i];
        if(fn == be)
        {
            continue;
        }
        if(u[fn] == 1)
        {
            fou = 1;
            break;
        }
        cva = re(fn,cn);
        if(cva == 1)
        {
            fou = 1;
            break;
        }
    }
    u[cn] = 0;
    if(fou == 1)
    {
        cyc[cn] = 1;
        if(thi[cn] == 1 || of == 1)
        {
            inn[ruc] = cn;
            ruc ++;
        }
    }
    return fou;
}
void Init(int nn)
{
    int i,j;
    n = nn;
    for(i=0; i<n; i++)
    {
        ggr[i] = i;
        see[i] = i;
        cyc[i] = 0;
    }
    rus = n;
}
void Link(int cl, int cr)
{
    int gl = figr(cl),gr = figr(cr),f,cru,cruc,i,j;
    pat[cl].push_back(cr);
    pat[cr].push_back(cl);
    deg[cl] ++;
    deg[cr] ++;
    mer(gl,gr);
    if(rus == 0)
    {
        return ;
    }
    ruc = 0;
    if(deg[cl] < deg[cr])
    {
        f = cl;
        cl = cr;
        cr = f;
        f = gl;
        gl = gr;
        gr = f;
    }
    if(deg[cl] > 3)
    {
            if(deg[cr] > 3)
            {
                rus = 0;
                return ;
            }
            else
            {
                ruc = 1;
                inn[0] = cl;
            }
    }
    else         
    {
        if(gl != gr)
        {
            if(deg[cl] > 3)
            {
                if(deg[cr] > 3)
                {
                    rus = 0;
                    return ;
                }
                else
                {
                    ruc = 1;
                    inn[0] = cl;
                }
            }
            else if(deg[cl] == 3)
            {
                if(deg[cr] == 3)
                {
                    ruc = 2;
                    inn[0] = cl;
                    inn[1] = cr;
                }
                else 
                {
                    for(i=0; i<3; i++)
                    {
                        inn[i] = pat[cl][i];
                    }
                    inn[3] = cl;
                    ruc = 4;
                }
            }
            else 
            {
                return ;
            }
        }
        else 
        {
            if(deg[cl] == 3)
            {
                if(deg[cr] == 3)
                {
                    ruc = 2;
                    inn[0] = cl;
                    inn[1] = cr;
                    for(i=0; i<2; i++)
                    {
                        for(j=0; j<2; j++)
                        {
                            if(pat[cl][i] == pat[cr][j])
                            {
                                ruc = 3;
                                inn[2] = pat[cl][i];
                            }
                        }
                    }
                }
                else 
                {
                    for(i=0; i<3; i++)
                    {
                        thi[pat[cl][i]] = 1;
                    }
                    ocy = 0;
                    // inn[0] = cl;
                    ruc = 0;
                    of = 0;
                    re(cr,cl);
                    if(ocy == 1)
                    {
                        re(cl,cr);
                    }
                }
            }
            else 
            {
                // inn[0] = cr;
                ocy = 0;
                ruc = 0;
                of = 1;
                re(cr,cl);
                if(ocy == 1)
                {
                    inn[0] = ret;
                    ruc = 1;
                    re(cl,cr);
                    if(ret != inn[0])
                    {
                        inn[1] = ret;
                        ruc = 2;
                    }
                }
            }
        }
    }
    sort(inn,inn+ruc);
    cru = 0;
    cruc = 0;
    for(i=0; i<rus; i++)
    {
        while(cruc < ruc && see[i] > inn[cruc])
        {
            cruc ++;
        }
        if(cruc < ruc && see[i] == inn[cruc])
        {
            see[cru] = see[i];
            cru ++;
        }
    }
    rus = cru;
    return ;
}

int CountCritical()
{
    return rus;
}

Compilation message

rings.cpp: In function 'int re(int, int)':
rings.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(i=0; i<pat[cn].size(); i++)
      |              ~^~~~~~~~~~~~~~~
rings.cpp:41:11: warning: unused variable 'j' [-Wunused-variable]
   41 |     int i,j,fn,fou = 0,cva;
      |           ^
rings.cpp: In function 'void Init(int)':
rings.cpp:82:11: warning: unused variable 'j' [-Wunused-variable]
   82 |     int i,j;
      |           ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94228 KB Output is correct
2 Correct 46 ms 94444 KB Output is correct
3 Correct 45 ms 94492 KB Output is correct
4 Correct 44 ms 94304 KB Output is correct
5 Correct 51 ms 94496 KB Output is correct
6 Correct 45 ms 94892 KB Output is correct
7 Correct 44 ms 94348 KB Output is correct
8 Correct 45 ms 94432 KB Output is correct
9 Correct 45 ms 94504 KB Output is correct
10 Correct 45 ms 94588 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 125512 KB Output is correct
2 Correct 657 ms 142504 KB Output is correct
3 Correct 662 ms 149868 KB Output is correct
4 Correct 736 ms 156092 KB Output is correct
5 Correct 721 ms 160156 KB Output is correct
6 Correct 931 ms 196960 KB Output is correct
7 Correct 664 ms 148744 KB Output is correct
8 Correct 653 ms 150696 KB Output is correct
9 Correct 712 ms 154444 KB Output is correct
10 Correct 476 ms 156500 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94228 KB Output is correct
2 Correct 46 ms 94444 KB Output is correct
3 Correct 45 ms 94492 KB Output is correct
4 Correct 44 ms 94304 KB Output is correct
5 Correct 51 ms 94496 KB Output is correct
6 Correct 45 ms 94892 KB Output is correct
7 Correct 44 ms 94348 KB Output is correct
8 Correct 45 ms 94432 KB Output is correct
9 Correct 45 ms 94504 KB Output is correct
10 Correct 45 ms 94588 KB Output is correct
11 Incorrect 45 ms 94556 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94228 KB Output is correct
2 Correct 46 ms 94444 KB Output is correct
3 Correct 45 ms 94492 KB Output is correct
4 Correct 44 ms 94304 KB Output is correct
5 Correct 51 ms 94496 KB Output is correct
6 Correct 45 ms 94892 KB Output is correct
7 Correct 44 ms 94348 KB Output is correct
8 Correct 45 ms 94432 KB Output is correct
9 Correct 45 ms 94504 KB Output is correct
10 Correct 45 ms 94588 KB Output is correct
11 Incorrect 45 ms 94556 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94228 KB Output is correct
2 Correct 46 ms 94444 KB Output is correct
3 Correct 45 ms 94492 KB Output is correct
4 Correct 44 ms 94304 KB Output is correct
5 Correct 51 ms 94496 KB Output is correct
6 Correct 45 ms 94892 KB Output is correct
7 Correct 44 ms 94348 KB Output is correct
8 Correct 45 ms 94432 KB Output is correct
9 Correct 45 ms 94504 KB Output is correct
10 Correct 45 ms 94588 KB Output is correct
11 Correct 257 ms 125512 KB Output is correct
12 Correct 657 ms 142504 KB Output is correct
13 Correct 662 ms 149868 KB Output is correct
14 Correct 736 ms 156092 KB Output is correct
15 Correct 721 ms 160156 KB Output is correct
16 Correct 931 ms 196960 KB Output is correct
17 Correct 664 ms 148744 KB Output is correct
18 Correct 653 ms 150696 KB Output is correct
19 Correct 712 ms 154444 KB Output is correct
20 Correct 476 ms 156500 KB Output is correct
21 Incorrect 45 ms 94556 KB Output isn't correct
22 Halted 0 ms 0 KB -