oj.uz

Submission #27395

# Submission time Handle Problem Language Result Execution time Memory
27395 2017-07-12T11:50:21 Z repeating Parachute rings (IOI12_rings) C++11
0 / 100
 4000 ms 7036 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define P push
#define pb push_back
#define MEM(dp,i) memset(dp,i,sizeof(dp))
#define W while
#define R return
#define C continue
#define SI size()
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define SF(x) scanf("%I64d",&x)
#define SF2(x,y) scanf("%I64d%I64d",&x,&y)
#define SF3(x,y,z) scanf("%I64d%I64d%I64d",&x,&y,&z)
#define SF4(x,y,z,o) scanf("%I64d%I64d%I64d%I64d",&x,&y,&z,&o)
#define all(v) v.begin(),v.end()

using namespace std;
const long long INF = 1e9+5e8;
const int MX=100005;

int n,par[MX],lvl[MX],cur,t[MX],res,dp[30][MX],up[MX],visit[MX];
vector<int> adj[MX];
bool is[MX];
void ADD(int node){
    if(visit[node]==cur)R;
    visit[node]=cur;
    t[node]++;
    if(t[node]==cur)res++;
}
void DSU(int x){
    if(x==par[x])R;
    DSU(par[x]);
    lvl[x]+=lvl[par[x]];
    par[x]=par[par[x]];
}
void build(int node){
    if(adj[node].SI==3){
        res=0;
        cur++;
        ADD(node);
        for(auto i : adj[node])
            ADD(i);
    }
    if(adj[node].SI>3){
        res=0;
        cur++;
        ADD(node);
    }
    DSU(node);
}
void get_up(int A,int B){
    res=0;
    cur++;
    if(lvl[A]<lvl[B]){
        swap(A,B);
    }
    W(lvl[A]>lvl[B]){
        ADD(A);
        is[A]=1;
        A=up[A];
    }
    W(A!=B){
        ADD(A);
        ADD(B);
        is[A]=1;
        is[B]=1;
        A=up[A];
        B=up[B];
    }
    is[A]=1;
    ADD(A);
    R;
}
void Init(int N_) {
    n=N_;
    res=n;
    for(int i=0;i<n;i++)
        par[i]=i,up[i]=i;
}

void Link(int A, int B) {
    if(res==0)R;
    adj[A].pb(B);
    adj[B].pb(A);
    build(A);
    build(B);
    if(par[A]==par[B]){
//        cout<<'s';
        if(res){
            if(is[A]&&is[B]){
                cur++;
                res=0;
                ADD(A);
                ADD(B);
                R;
            }
            get_up(A,B);
        }
        else{

        }
    }
    else{
        par[par[A]]=par[B];
        up[A]=B;
        dp[0][A]=B;
    }
}

int CountCritical() {

  return res;

}
/*
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define inbuf_len 1 << 16
#define outbuf_len 1 << 16

void Init(int N);
int CountCritical();
void Link(int a, int b);

int main() {
  int tmp;

  Set input and output buffering
  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();
      cout<<critical<<endl;
    } else {
      tmp = scanf("%d", &B);
      assert(tmp == 1);
      Link(A, B);
    }
  }

  return 0;
}

*/

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 6 ms 3064 KB Output is correct
3 Correct 6 ms 3064 KB Output is correct
4 Execution timed out 4006 ms 3064 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 7036 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 6 ms 3064 KB Output is correct
3 Correct 6 ms 3064 KB Output is correct
4 Execution timed out 4006 ms 3064 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 6 ms 3064 KB Output is correct
3 Correct 6 ms 3064 KB Output is correct
4 Execution timed out 4006 ms 3064 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 6 ms 3064 KB Output is correct
3 Correct 6 ms 3064 KB Output is correct
4 Execution timed out 4006 ms 3064 KB Time limit exceeded
5 Halted 0 ms 0 KB -