답안 #66000 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66000	2018-08-09T10:42:57 Z	Bodo171	낙하산 고리들 (IOI12_rings)	C++14	100 / 100	1503 ms	110444 KB

rings

#include <iostream>
#include <vector>

using namespace std;
const int nmax=1000*1000+5;
int n;
pair<int,int> muchii[nmax];
vector<int> v[nmax];
int grad[nmax],special[nmax],valid[nmax];
int nodspecial[10],auxiliare[10],ab[10],abaux[10];
int maimari,busit,mme,gradmx,speciale,nr,auxi,eq3;
struct linker
{
    int ciclu,wciclu,mxout;
    char gr[nmax];
    int tt[nmax],rg[nmax];
    void ini()
    {
        for(int i=0;i<n;i++)
            tt[i]=i,rg[i]=1;
    }
    int finds(int x)
    {
        int y=x,aux=0;
        while(x!=tt[x])
            x=tt[x];
        while(y!=x)
        {
            aux=tt[y];
            tt[y]=x;
            y=aux;
        }
        return x;
    }
    void unite(int A,int B)
    {
        if(rg[A]>rg[B]) {tt[B]=A;rg[A]+=rg[B];}
        else {tt[A]=B;rg[B]+=rg[A];}
    }
    void uneste(int x,int y)
    {
        gr[x]++;gr[y]++;
        if(gr[x]>mxout) mxout=(int)gr[x];
        if(gr[y]>mxout) mxout=(int)gr[y];
        if(finds(x)==finds(y))
            ciclu+=1,wciclu=rg[finds(x)];
        else unite(finds(x),finds(y));
    }
}li[5];
void specialul(int x)
{
    speciale++;nodspecial[speciale]=x;
     ab[speciale]=0;
     li[speciale].mxout=0;li[speciale].ciclu=0;li[speciale].wciclu=0;
     li[speciale].ini();
    for(int i=0;i<n;i++)
        li[speciale].gr[i]=0;
    for(int i=1;i<=nr;i++)
        if(muchii[i].first!=x&&muchii[i].second!=x)
            li[speciale].uneste(muchii[i].first,muchii[i].second);
    special[x]=speciale;
}
void spec(int x)
{
    if(grad[x]==4)
    {
        maimari++;
        if(maimari>1)
        {
            busit=1;
            return;
        }
    }
    if(grad[x]>=gradmx&&grad[x]>=3)
    {
        if(grad[x]==3)
        {
            gradmx=3;eq3++;
            if(eq3>4) busit=1;
            if(!speciale)
            {
                specialul(x);
                for(int i=0;i<v[x].size();i++)
                    specialul(v[x][i]);
            }
            return;
        }
        else
        {
            gradmx=grad[x];
            if(grad[x]>3)
            {
                if(speciale!=special[x])
                {
                    speciale=0;
                    specialul(x);
                }
            }
        }
    }
}
void Init(int N_) {

  n = N_;
  li[0].ini();

}

void Link(int A, int B) {
    if(busit) return;
    grad[A]++;
    grad[B]++;
    if(gradmx<3)
    {
     v[A].push_back(B);
     v[B].push_back(A);
    }
    spec(A);
    spec(B);
    muchii[++nr]={A,B};
    for(int i=(speciale!=0);i<=speciale;i++)
        if((!ab[i]))
        if(i==0||(nodspecial[i]!=A&&nodspecial[i]!=B))
           li[i].uneste(A,B);
    for(int i=1;i<=speciale;i++)
        if(li[i].mxout>=3||li[i].ciclu)
          ab[i]=1;
}

int CountCritical() {
  if(busit)
  {
      return 0;
  }
  if(gradmx<3)
  {
      if(li[0].ciclu>1)
      {
          busit=1;
          return 0;
      }
      if(li[0].ciclu==1)
        return li[0].wciclu;
      return n;
  }
  int ret=0;
  for(int i=1;i<=speciale;i++)
  {
    if((!li[i].ciclu)&&li[i].mxout<3) ret++;
    else ab[i]=1;
  }
  if(ret==0) busit=1;
  return ret;

}

Compilation message

rings.cpp: In function 'void spec(int)':
rings.cpp:83:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int i=0;i<v[x].size();i++)
                             ~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	23800 KB	Output is correct
2	Correct	24 ms	24308 KB	Output is correct
3	Correct	24 ms	24344 KB	Output is correct
4	Correct	23 ms	24344 KB	Output is correct
5	Correct	24 ms	24344 KB	Output is correct
6	Correct	23 ms	24344 KB	Output is correct
7	Correct	21 ms	24440 KB	Output is correct
8	Correct	24 ms	24440 KB	Output is correct
9	Correct	24 ms	24756 KB	Output is correct
10	Correct	25 ms	24756 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	487 ms	51080 KB	Output is correct
2	Correct	727 ms	82764 KB	Output is correct
3	Correct	355 ms	82764 KB	Output is correct
4	Correct	1327 ms	82764 KB	Output is correct
5	Correct	1291 ms	82764 KB	Output is correct
6	Correct	1266 ms	82764 KB	Output is correct
7	Correct	344 ms	82764 KB	Output is correct
8	Correct	1296 ms	102776 KB	Output is correct
9	Correct	1503 ms	110444 KB	Output is correct
10	Correct	981 ms	110444 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	23800 KB	Output is correct
2	Correct	24 ms	24308 KB	Output is correct
3	Correct	24 ms	24344 KB	Output is correct
4	Correct	23 ms	24344 KB	Output is correct
5	Correct	24 ms	24344 KB	Output is correct
6	Correct	23 ms	24344 KB	Output is correct
7	Correct	21 ms	24440 KB	Output is correct
8	Correct	24 ms	24440 KB	Output is correct
9	Correct	24 ms	24756 KB	Output is correct
10	Correct	25 ms	24756 KB	Output is correct
11	Correct	25 ms	110444 KB	Output is correct
12	Correct	29 ms	110444 KB	Output is correct
13	Correct	28 ms	110444 KB	Output is correct
14	Correct	24 ms	110444 KB	Output is correct
15	Correct	25 ms	110444 KB	Output is correct
16	Correct	27 ms	110444 KB	Output is correct
17	Correct	25 ms	110444 KB	Output is correct
18	Correct	27 ms	110444 KB	Output is correct
19	Correct	27 ms	110444 KB	Output is correct
20	Correct	27 ms	110444 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	23800 KB	Output is correct
2	Correct	24 ms	24308 KB	Output is correct
3	Correct	24 ms	24344 KB	Output is correct
4	Correct	23 ms	24344 KB	Output is correct
5	Correct	24 ms	24344 KB	Output is correct
6	Correct	23 ms	24344 KB	Output is correct
7	Correct	21 ms	24440 KB	Output is correct
8	Correct	24 ms	24440 KB	Output is correct
9	Correct	24 ms	24756 KB	Output is correct
10	Correct	25 ms	24756 KB	Output is correct
11	Correct	25 ms	110444 KB	Output is correct
12	Correct	29 ms	110444 KB	Output is correct
13	Correct	28 ms	110444 KB	Output is correct
14	Correct	24 ms	110444 KB	Output is correct
15	Correct	25 ms	110444 KB	Output is correct
16	Correct	27 ms	110444 KB	Output is correct
17	Correct	25 ms	110444 KB	Output is correct
18	Correct	27 ms	110444 KB	Output is correct
19	Correct	27 ms	110444 KB	Output is correct
20	Correct	27 ms	110444 KB	Output is correct
21	Correct	43 ms	110444 KB	Output is correct
22	Correct	59 ms	110444 KB	Output is correct
23	Correct	69 ms	110444 KB	Output is correct
24	Correct	57 ms	110444 KB	Output is correct
25	Correct	40 ms	110444 KB	Output is correct
26	Correct	57 ms	110444 KB	Output is correct
27	Correct	75 ms	110444 KB	Output is correct
28	Correct	52 ms	110444 KB	Output is correct
29	Correct	51 ms	110444 KB	Output is correct
30	Correct	95 ms	110444 KB	Output is correct

Subtask #5
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	23800 KB	Output is correct
2	Correct	24 ms	24308 KB	Output is correct
3	Correct	24 ms	24344 KB	Output is correct
4	Correct	23 ms	24344 KB	Output is correct
5	Correct	24 ms	24344 KB	Output is correct
6	Correct	23 ms	24344 KB	Output is correct
7	Correct	21 ms	24440 KB	Output is correct
8	Correct	24 ms	24440 KB	Output is correct
9	Correct	24 ms	24756 KB	Output is correct
10	Correct	25 ms	24756 KB	Output is correct
11	Correct	487 ms	51080 KB	Output is correct
12	Correct	727 ms	82764 KB	Output is correct
13	Correct	355 ms	82764 KB	Output is correct
14	Correct	1327 ms	82764 KB	Output is correct
15	Correct	1291 ms	82764 KB	Output is correct
16	Correct	1266 ms	82764 KB	Output is correct
17	Correct	344 ms	82764 KB	Output is correct
18	Correct	1296 ms	102776 KB	Output is correct
19	Correct	1503 ms	110444 KB	Output is correct
20	Correct	981 ms	110444 KB	Output is correct
21	Correct	25 ms	110444 KB	Output is correct
22	Correct	29 ms	110444 KB	Output is correct
23	Correct	28 ms	110444 KB	Output is correct
24	Correct	24 ms	110444 KB	Output is correct
25	Correct	25 ms	110444 KB	Output is correct
26	Correct	27 ms	110444 KB	Output is correct
27	Correct	25 ms	110444 KB	Output is correct
28	Correct	27 ms	110444 KB	Output is correct
29	Correct	27 ms	110444 KB	Output is correct
30	Correct	27 ms	110444 KB	Output is correct
31	Correct	43 ms	110444 KB	Output is correct
32	Correct	59 ms	110444 KB	Output is correct
33	Correct	69 ms	110444 KB	Output is correct
34	Correct	57 ms	110444 KB	Output is correct
35	Correct	40 ms	110444 KB	Output is correct
36	Correct	57 ms	110444 KB	Output is correct
37	Correct	75 ms	110444 KB	Output is correct
38	Correct	52 ms	110444 KB	Output is correct
39	Correct	51 ms	110444 KB	Output is correct
40	Correct	95 ms	110444 KB	Output is correct
41	Correct	288 ms	110444 KB	Output is correct
42	Correct	629 ms	110444 KB	Output is correct
43	Correct	283 ms	110444 KB	Output is correct
44	Correct	344 ms	110444 KB	Output is correct
45	Correct	484 ms	110444 KB	Output is correct
46	Correct	825 ms	110444 KB	Output is correct
47	Correct	1130 ms	110444 KB	Output is correct
48	Correct	327 ms	110444 KB	Output is correct
49	Correct	830 ms	110444 KB	Output is correct
50	Correct	890 ms	110444 KB	Output is correct
51	Correct	288 ms	110444 KB	Output is correct
52	Correct	336 ms	110444 KB	Output is correct
53	Correct	293 ms	110444 KB	Output is correct
54	Correct	1068 ms	110444 KB	Output is correct
55	Correct	643 ms	110444 KB	Output is correct

답안 #66000

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 17.0 / 17.0

Subtask #3 18.0 / 18.0

Subtask #4 14.0 / 14.0

Subtask #5 31.0 / 31.0

Subtask #1
20.0 / 20.0

Subtask #2
17.0 / 17.0

Subtask #3
18.0 / 18.0

Subtask #4
14.0 / 14.0

Subtask #5
31.0 / 31.0