oj.uz

답안 #382377

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
382377 2021-03-27T07:55:29 Z mehrdad_sohrabi 낙하산 고리들 (IOI12_rings) C++14
20 / 100
 1798 ms 107532 KB 
#include <bits/stdc++.h>
/// 500 485 462 A4
using namespace std;
typedef int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
const int MAXN=1e6+100;
map <pii,int> mp;
vector <int> g[MAXN];
ll vis[MAXN];
vector <int> dig;
ll td=0;
ll p1=1;
ll ans=MAXN;
ll t4=0;
ll hazf[MAXN];
ll n;
ll ch[MAXN];
ll cnt=0;
vector <int> W;
ll par[MAXN];
void del(ll v){
    for (int i=0;i<n;i++){
        vector <int> a;
        for (auto u : g[i]) if (u!=v) a.pb(u);
        g[i]=a;
    }
    g[v].clear();
    hazf[v]=1;
}
void Init(ll N){
    n=N;
    ans=n;
    for (int i=0;i<N;i++){
        par[i]=i;
    }
}
ll getpar(ll v){
    if (par[v]==v) return v;
    return par[v]=getpar(par[v]);
}
void rebuild(){
    for (int i=0;i<MAXN;i++){
        par[i]=i;
    }
    ans=1;
    for (int i=0;i<n;i++) if (g[i].size()>2) p1=0;
    for (int v=0;v<n;v++){
        for (auto u : g[v]){
            if (u>v){
                ll u1=getpar(u);
                ll v1=getpar(v);
                if (u1==v1){
                    p1=0;
                }
                par[u1]=v1;
            }
        }
    }
}
ll pa[MAXN];
ll hi[MAXN];
void dfs(ll v,ll p){
    vis[v]=1;
    hi[v]=hi[p]+1;
    pa[v]=p;
    for (auto u : g[v]){
        if (u==p) continue;
        if (vis[u]==1 && hi[u]>hi[v]){
            ll z=u;
            while(z!=v){
                ch[z]++;
                if (ch[z]==cnt) ans++,W.pb(z);
                z=pa[z];
            }
            ch[v]++;
            if (ch[v]==cnt) ans++,W.pb(v);
            continue;
        }
        if (vis[u]) continue;
        dfs(u,v);
    }
}
void Link(int A, int B) {
    if (p1==0) return ;
    if (hazf[A] || hazf[B]) return ;
    g[A].pb(B);
    g[B].pb(A);
    mp[{A,B}]=1;
    mp[{B,A}]=1;
    if (t4==1){
        if (g[A].size()==g[B].size()){
            p1=0;
        }
        if (getpar(A)==getpar(B)) p1=0;
    }
    if (p1==0) return ;
//        cout << "GOOOZ" << endl;
    if (t4==1 && (g[A].size()>2 || g[B].size()>2)){
        p1=0;
        return ;
    }
    if (g[A].size()>3){
        del(A);
        rebuild();
    }
    if (g[B].size()>3){
        del(A);
        rebuild();
    }
    if (getpar(A)==getpar(B)){
    //    cout << "GOOZ" << endl;
        if (td==0){
            td++;
            ans=0;
            W.clear();
            cnt++;
            for (int i=0;i<n;i++){
                if (vis[i]==0) dfs(i,i);
            }
        }
        else if (td==1 && t4==0){
            p1=0;
        }
    }
    else{
        par[par[A]]=par[B];
    }
    if (g[B].size()==3){
    //    cout << "NR " << B << endl;
        cnt++;
        ans=0;
        W.clear();
        for (auto u : g[B]){
            ch[u]++;
            if (ch[u]==cnt) {
                ans++;
                W.pb(u);
       //         cout << u << " RAS " << endl;
            }
        }
        ch[B]++;
       // cout << ch[B] << " ascw" << endl;
        if (ch[B]==cnt) W.pb(B),ans++;
    }
    if (g[A].size()==3){
    //    cout << " iurfrg " << endl;
        cnt++;
        ans=0;
        W.clear();
        for (auto u : g[A]){
            ch[u]++;
            if (ch[u]==cnt) {
                ans++;
                W.pb(u);
            }
        }
        ch[A]++;
        if (ch[A]==cnt) W.pb(A),ans++;
    }

}

int CountCritical() {
    if (p1==0) return 0;
    if (t4) return 1;
    return ans;
}

/*
int main() {
  int tmp;

  char *inbuf, *outbuf;
  inbuf = (char*) malloc(inbuf_len * sizeof(char));
  outbuf = (char*) malloc(outbuf_len * sizeof(char));
  tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
  tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);

  int N, L;
  tmp = scanf("%d %d", &N, &L);
  assert(tmp == 2);
  Init(N);

  int i;
  for (i = 0; i < L; i++) {
    int A, B;
    tmp = scanf("%d", &A);
    if (A == -1) {
      int critical;
      critical = CountCritical();
      printf("%d ans\n", critical);
    } else {
      tmp = scanf("%d", &B);
      assert(tmp == 1);
      Link(A, B);
    }
  }

  return 0;

}
*/

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 23788 KB Output is correct
2 Correct 27 ms 28396 KB Output is correct
3 Correct 24 ms 28524 KB Output is correct
4 Correct 18 ms 24044 KB Output is correct
5 Correct 20 ms 24556 KB Output is correct
6 Correct 22 ms 25196 KB Output is correct
7 Correct 17 ms 24044 KB Output is correct
8 Correct 24 ms 24556 KB Output is correct
9 Correct 23 ms 24684 KB Output is correct
10 Correct 22 ms 24684 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1798 ms 107532 KB Output is correct
2 Incorrect 1251 ms 80752 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 23788 KB Output is correct
2 Correct 27 ms 28396 KB Output is correct
3 Correct 24 ms 28524 KB Output is correct
4 Correct 18 ms 24044 KB Output is correct
5 Correct 20 ms 24556 KB Output is correct
6 Correct 22 ms 25196 KB Output is correct
7 Correct 17 ms 24044 KB Output is correct
8 Correct 24 ms 24556 KB Output is correct
9 Correct 23 ms 24684 KB Output is correct
10 Correct 22 ms 24684 KB Output is correct
11 Incorrect 21 ms 24684 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 23788 KB Output is correct
2 Correct 27 ms 28396 KB Output is correct
3 Correct 24 ms 28524 KB Output is correct
4 Correct 18 ms 24044 KB Output is correct
5 Correct 20 ms 24556 KB Output is correct
6 Correct 22 ms 25196 KB Output is correct
7 Correct 17 ms 24044 KB Output is correct
8 Correct 24 ms 24556 KB Output is correct
9 Correct 23 ms 24684 KB Output is correct
10 Correct 22 ms 24684 KB Output is correct
11 Incorrect 21 ms 24684 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 23788 KB Output is correct
2 Correct 27 ms 28396 KB Output is correct
3 Correct 24 ms 28524 KB Output is correct
4 Correct 18 ms 24044 KB Output is correct
5 Correct 20 ms 24556 KB Output is correct
6 Correct 22 ms 25196 KB Output is correct
7 Correct 17 ms 24044 KB Output is correct
8 Correct 24 ms 24556 KB Output is correct
9 Correct 23 ms 24684 KB Output is correct
10 Correct 22 ms 24684 KB Output is correct
11 Correct 1798 ms 107532 KB Output is correct
12 Incorrect 1251 ms 80752 KB Output isn't correct
13 Halted 0 ms 0 KB -