Submission #1037137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037137		8pete8	Parachute rings (IOI12_rings)	C++17	100 / 100	537 ms	122728 KiB

rings

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
using namespace std;
const int mod=1e9+7,mxn=1e6+5,inf=1e9,minf=-1e9,lg=25;
int n;
vector<int>adj[mxn+10];
int found=-1;
struct dsu{
  int pa[mxn+10],ans=1,deg[mxn+10],sz[mxn+10];
  void init(){ans=1;for(int i=0;i<n;i++)pa[i]=i,deg[i]=0,sz[i]=1;}
  int find(int u){
    return (pa[u]==u)?u:pa[u]=find(pa[u]);
  }
  bool merg(int a,int b){
    int x=a,y=b;
    a=find(a),b=find(b);
    deg[x]++,deg[y]++;
    if(deg[x]==3||deg[y]==3)ans=0;
    if(a==b){
      ans=0;
      return 0;
    }
    pa[a]=b;
    sz[b]+=sz[a];
    return 1;
  }
}t[6];
vector<pii>event;
vector<int>have;
int havecycle=-1,why=0;
void Init(int N_){
  if(why)assert(0);
  found=-1;
  why++;
  havecycle=-1;
  n=N_;
  t[0].init();
}
void make(int node,int pos){
  t[pos].init();
  for(auto i:event)if(i.f!=node&&i.s!=node)t[pos].merg(i.f,i.s);
}
void Link(int a,int b){
  if(found!=-1){
    for(int i=0;i<have.size();i++)if(a!=have[i]&&b!=have[i])t[i+1].merg(a,b);
  }
  else{
    event.pb({a,b});
    if(t[0].merg(a,b)==0){
      if(havecycle==-1)havecycle=t[0].sz[t[0].find(b)];
      else havecycle=-2;
    }
    adj[a].pb(b);
    adj[b].pb(a);
    if(t[0].deg[a]==3)found=a;
    else if(t[0].deg[b]==3)found=b;
    if(found!=-1){
      have.pb(found);
      for(auto i:adj[found])have.pb(i);
      for(int i=0;i<have.size();i++)make(have[i],i+1);
    }
  } 
}
int CountCritical(){
  if(found!=-1){
    int sum=0;
    for(int i=0;i<have.size();i++)sum+=t[i+1].ans;
    return sum;
  }
  else if(havecycle==-2)return 0;
  else if(havecycle!=-1)return havecycle;
  return n;
}
 
/*
if we can find intersect from all these set:
1. in every cycle
2. have deg >=3
3. directly connected to deg 3
if there are no deg>3 then there can be atmost 4 candidates
because the node has to be directly connected to all deg 3 and every node deg<=3
if theres a node deg>3 we just have to check 1 node but the deg can be a lot
 
how to know if a node is in cycle?
*/

Compilation message (stderr)

rings.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
rings.cpp:40:13: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   40 |   void init(){ans=1;for(int i=0;i<n;i++)pa[i]=i,deg[i]=0,sz[i]=1;}
      |             ^
rings.cpp:41:17: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   41 |   int find(int u){
      |                 ^
rings.cpp:44:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   44 |   bool merg(int a,int b){
      |                        ^
rings.cpp:61:17: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   61 | void Init(int N_){
      |                 ^
rings.cpp:69:27: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   69 | void make(int node,int pos){
      |                           ^
rings.cpp:73:22: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   73 | void Link(int a,int b){
      |                      ^
rings.cpp: In function 'void Link(int, int)':
rings.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i=0;i<have.size();i++)if(a!=have[i]&&b!=have[i])t[i+1].merg(a,b);
      |                 ~^~~~~~~~~~~~
rings.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |       for(int i=0;i<have.size();i++)make(have[i],i+1);
      |                   ~^~~~~~~~~~~~
rings.cpp: At global scope:
rings.cpp:94:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   94 | int CountCritical(){
      |                   ^
rings.cpp: In function 'int CountCritical()':
rings.cpp:97:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int i=0;i<have.size();i++)sum+=t[i+1].ans;
      |                 ~^~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 31 / 31