제출 #145637

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
145637	2019-08-20 14:47:15	TadijaSebez	Collapse (JOI18_collapse)	C++11	100 / 100	7133 ms	23668 KiB

collapse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
const int S=317;
struct DSU
{
  int p[N],z[N],n,cmp,S[N],c;
  void init(int _n){ n=_n;for(int i=1;i<=n;i++) p[i]=i,z[i]=1;cmp=n;c=0;}
  DSU(){}
  int Find(int x){ return p[x]==x?x:Find(p[x]);}
  void Union(int x, int y, bool bck)
  {
    x=Find(x);y=Find(y);
    if(x==y){ if(bck) S[++c]=0;return;}
    cmp--;
    if(z[x]>z[y]) swap(x,y);
    p[x]=y;
    z[y]+=z[x];
    S[++c]=x;
  }
  void Undo()
  {
    if(!S[c]) c--;
    else
    {
      cmp++;
      int x=S[c--];
            z[p[x]]-=z[x];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

컴파일 시 표준 에러 (stderr) 메시지

collapse.cpp: In function 'std::vector<int> Solve()':
collapse.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(e_ptr<now.size() && y[now[e_ptr]]==i) DS.Union(x[now[e_ptr]],y[now[e_ptr]],0),e_ptr++;
          ~~~~~^~~~~~~~~~~
collapse.cpp:65:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(q_ptr<qs.size() && p[qs[q_ptr]]==i)
          ~~~~~^~~~~~~~~~
collapse.cpp:81:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(e_ptr<now.size() && x[now[e_ptr]]==i) DS.Union(x[now[e_ptr]],y[now[e_ptr]],0),e_ptr++;
          ~~~~~^~~~~~~~~~~
collapse.cpp:82:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(q_ptr<qs.size() && p[qs[q_ptr]]==i-1)
          ~~~~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35