oj.uz

Submission #382418

# Submission time Handle Problem Language Result Execution time Memory
382418 2021-03-27T09:41:08 Z mehrdad_sohrabi Parachute rings (IOI12_rings) C++14
100 / 100
 1406 ms 127076 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 tool=0;
ll n;
ll ch[MAXN];
ll cnt=0;
vector <int> W;
ll par[MAXN];
ll dor[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];
ll mark[MAXN];
ll dd(ll v,ll p){
    mark[v]=1;
    if (dor[v]==1) return v;
    for (auto u : g[v]){
        if (u==p || mark[v]) continue;
        return dd(u,v);
    }
    return -1;
}
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]++;
                tool++;
                dor[z]=1;
                if (ch[z]==cnt) ans++,W.pb(z);
                z=pa[z];
            }
            tool++;
            dor[v]=1;
            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 || ans==0) return ;
    if (hazf[A] || hazf[B]) return ;
    g[A].pb(B);
    g[B].pb(A);

    if (g[B].size()==3){
    //    cout << "NR " << B << endl;
        cnt++;
        ans=0;
        W.clear();
        for (auto u : g[B]){
            ch[u]++;
            mp[{u,B}]=1;
            mp[{B,u}]=1;
            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]){
            mp[{u,A}]=1;
            mp[{A,u}]=1;
            ch[u]++;
            if (ch[u]==cnt) {
                ans++;
                W.pb(u);
            }
        }
        ch[A]++;
        if (ch[A]==cnt) W.pb(A),ans++;
    }
    if (t4==1){
        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){
            t4=1;
        del(A);
        rebuild();
        return ;
    }
    if (g[B].size()>3){
        t4=1;
        del(B);
        rebuild();
        return ;
    }
    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 {
            ll z=dd(A,B);
            ll tz=dd(B,A);

            if (mp.count({z,tz})){
                cnt++;
                W.clear();
                ans=0;
                ch[z]++;
                if (ch[z]==cnt) ans++;
                ch[tz]++;
                if (ch[tz]==cnt) ans++;
          //      cout << ans << " erij " << endl;
            }
            else p1=0;
        }

    }
    else{
        par[par[A]]=par[B];
    }

}

int CountCritical() {
    /*
    memset(vis,0,sizeof vis);
    for (int i=0;i<n;i++){
        if (vis[i]==0) dfs(i,i);
    }
    */
    if (t4) {
        return p1;
    }
    if (p1==0) return 0;
    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

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 21 ms 27884 KB Output is correct
3 Correct 21 ms 28012 KB Output is correct
4 Correct 17 ms 23936 KB Output is correct
5 Correct 18 ms 24172 KB Output is correct
6 Correct 20 ms 24556 KB Output is correct
7 Correct 18 ms 24044 KB Output is correct
8 Correct 18 ms 24172 KB Output is correct
9 Correct 19 ms 24044 KB Output is correct
10 Correct 19 ms 24044 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 42476 KB Output is correct
2 Correct 963 ms 52780 KB Output is correct
3 Correct 260 ms 28396 KB Output is correct
4 Correct 1304 ms 74076 KB Output is correct
5 Correct 1324 ms 82404 KB Output is correct
6 Correct 1406 ms 127076 KB Output is correct
7 Correct 251 ms 29932 KB Output is correct
8 Correct 949 ms 58476 KB Output is correct
9 Correct 1032 ms 60652 KB Output is correct
10 Correct 933 ms 80364 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 21 ms 27884 KB Output is correct
3 Correct 21 ms 28012 KB Output is correct
4 Correct 17 ms 23936 KB Output is correct
5 Correct 18 ms 24172 KB Output is correct
6 Correct 20 ms 24556 KB Output is correct
7 Correct 18 ms 24044 KB Output is correct
8 Correct 18 ms 24172 KB Output is correct
9 Correct 19 ms 24044 KB Output is correct
10 Correct 19 ms 24044 KB Output is correct
11 Correct 19 ms 24172 KB Output is correct
12 Correct 21 ms 24428 KB Output is correct
13 Correct 24 ms 28396 KB Output is correct
14 Correct 21 ms 28012 KB Output is correct
15 Correct 22 ms 27884 KB Output is correct
16 Correct 21 ms 24428 KB Output is correct
17 Correct 19 ms 24172 KB Output is correct
18 Correct 19 ms 24044 KB Output is correct
19 Correct 21 ms 24428 KB Output is correct
20 Correct 21 ms 24300 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 21 ms 27884 KB Output is correct
3 Correct 21 ms 28012 KB Output is correct
4 Correct 17 ms 23936 KB Output is correct
5 Correct 18 ms 24172 KB Output is correct
6 Correct 20 ms 24556 KB Output is correct
7 Correct 18 ms 24044 KB Output is correct
8 Correct 18 ms 24172 KB Output is correct
9 Correct 19 ms 24044 KB Output is correct
10 Correct 19 ms 24044 KB Output is correct
11 Correct 19 ms 24172 KB Output is correct
12 Correct 21 ms 24428 KB Output is correct
13 Correct 24 ms 28396 KB Output is correct
14 Correct 21 ms 28012 KB Output is correct
15 Correct 22 ms 27884 KB Output is correct
16 Correct 21 ms 24428 KB Output is correct
17 Correct 19 ms 24172 KB Output is correct
18 Correct 19 ms 24044 KB Output is correct
19 Correct 21 ms 24428 KB Output is correct
20 Correct 21 ms 24300 KB Output is correct
21 Correct 34 ms 25068 KB Output is correct
22 Correct 46 ms 25836 KB Output is correct
23 Correct 56 ms 26368 KB Output is correct
24 Correct 56 ms 29292 KB Output is correct
25 Correct 31 ms 28140 KB Output is correct
26 Correct 58 ms 29932 KB Output is correct
27 Correct 70 ms 27756 KB Output is correct
28 Correct 41 ms 25708 KB Output is correct
29 Correct 40 ms 24684 KB Output is correct
30 Correct 92 ms 30572 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 21 ms 27884 KB Output is correct
3 Correct 21 ms 28012 KB Output is correct
4 Correct 17 ms 23936 KB Output is correct
5 Correct 18 ms 24172 KB Output is correct
6 Correct 20 ms 24556 KB Output is correct
7 Correct 18 ms 24044 KB Output is correct
8 Correct 18 ms 24172 KB Output is correct
9 Correct 19 ms 24044 KB Output is correct
10 Correct 19 ms 24044 KB Output is correct
11 Correct 420 ms 42476 KB Output is correct
12 Correct 963 ms 52780 KB Output is correct
13 Correct 260 ms 28396 KB Output is correct
14 Correct 1304 ms 74076 KB Output is correct
15 Correct 1324 ms 82404 KB Output is correct
16 Correct 1406 ms 127076 KB Output is correct
17 Correct 251 ms 29932 KB Output is correct
18 Correct 949 ms 58476 KB Output is correct
19 Correct 1032 ms 60652 KB Output is correct
20 Correct 933 ms 80364 KB Output is correct
21 Correct 19 ms 24172 KB Output is correct
22 Correct 21 ms 24428 KB Output is correct
23 Correct 24 ms 28396 KB Output is correct
24 Correct 21 ms 28012 KB Output is correct
25 Correct 22 ms 27884 KB Output is correct
26 Correct 21 ms 24428 KB Output is correct
27 Correct 19 ms 24172 KB Output is correct
28 Correct 19 ms 24044 KB Output is correct
29 Correct 21 ms 24428 KB Output is correct
30 Correct 21 ms 24300 KB Output is correct
31 Correct 34 ms 25068 KB Output is correct
32 Correct 46 ms 25836 KB Output is correct
33 Correct 56 ms 26368 KB Output is correct
34 Correct 56 ms 29292 KB Output is correct
35 Correct 31 ms 28140 KB Output is correct
36 Correct 58 ms 29932 KB Output is correct
37 Correct 70 ms 27756 KB Output is correct
38 Correct 41 ms 25708 KB Output is correct
39 Correct 40 ms 24684 KB Output is correct
40 Correct 92 ms 30572 KB Output is correct
41 Correct 217 ms 35180 KB Output is correct
42 Correct 460 ms 44780 KB Output is correct
43 Correct 264 ms 32236 KB Output is correct
44 Correct 298 ms 43628 KB Output is correct
45 Correct 455 ms 61036 KB Output is correct
46 Correct 841 ms 65772 KB Output is correct
47 Correct 1174 ms 101544 KB Output is correct
48 Correct 249 ms 31596 KB Output is correct
49 Correct 694 ms 55156 KB Output is correct
50 Correct 701 ms 54832 KB Output is correct
51 Correct 293 ms 34156 KB Output is correct
52 Correct 330 ms 39404 KB Output is correct
53 Correct 218 ms 30828 KB Output is correct
54 Correct 843 ms 54596 KB Output is correct
55 Correct 927 ms 57216 KB Output is correct