oj.uz

Submission #1037104

# Submission time Handle Problem Language Result Execution time Memory
1037104 2024-07-28T05:21:45 Z 8pete8 Parachute rings (IOI12_rings) C++17
37 / 100
 676 ms 107860 KB 
#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,vis[mxn+10];
vector<int>adj[mxn+10];
int add[mxn+10],rem[mxn+10],cnt=0,on[mxn+10],cnt2=0,mx=0;
void clear(){
  for(int i=0;i<n;i++)add[i]=0,on[i]=0,vis[i]=0,rem[i]=0;
  cnt2=0,mx=0;
}
void Init(int N_) {
  n=N_;
  for(int i=0;i<n;i++)adj[i].clear();
}
void Link(int a,int b){
  adj[a].pb(b);
  adj[b].pb(a);
}
void dfs(int cur,int p){
  vis[cur]=on[cur]=1;
  for(auto i:adj[cur]){
    if(i==p)continue;
    if(vis[i]&&on[i])add[cur]++,rem[i]++,cnt++;
    if(!vis[i])dfs(i,cur),add[cur]+=(add[i]-rem[i]);
  }
  on[cur]=0;
}
int CountCritical(){
  clear();
  for(int i=0;i<n;i++){
    if(!vis[i]){
      cnt=0;
      dfs(i,-1);
      if(cnt)cnt2++;
    }
    mx=max(mx,add[i]);
  }
  if(cnt2>1)return 0;//atmost 1 comp with cycle
  int have=0;
  for(int i=0;i<n;i++)if(adj[i].size()>=3)have++;
  cnt=0;
  for(int i=0;i<n;i++){
    int x=(adj[i].size()>=3);
    for(auto j:adj[i])if(adj[j].size()==3)x++;
    if(x==have&&add[i]==mx)cnt++;
  }
  clear();
  return cnt;
}

/*
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

rings.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
rings.cpp:38:12: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   38 | void clear(){
      |            ^
rings.cpp:42:17: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   42 | void Init(int N_) {
      |                 ^
rings.cpp:46:22: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   46 | void Link(int a,int b){
      |                      ^
rings.cpp:50:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   50 | void dfs(int cur,int p){
      |                       ^
rings.cpp:59:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   59 | int CountCritical(){
      |                   ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31064 KB Output is correct
2 Correct 5 ms 31324 KB Output is correct
3 Correct 5 ms 31324 KB Output is correct
4 Correct 4 ms 31192 KB Output is correct
5 Correct 5 ms 31324 KB Output is correct
6 Correct 5 ms 31580 KB Output is correct
7 Correct 4 ms 31068 KB Output is correct
8 Correct 5 ms 31324 KB Output is correct
9 Correct 5 ms 31324 KB Output is correct
10 Correct 8 ms 31324 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 54052 KB Output is correct
2 Correct 493 ms 64084 KB Output is correct
3 Correct 545 ms 84816 KB Output is correct
4 Correct 632 ms 71504 KB Output is correct
5 Correct 676 ms 72384 KB Output is correct
6 Correct 662 ms 107860 KB Output is correct
7 Correct 497 ms 82256 KB Output is correct
8 Correct 604 ms 68688 KB Output is correct
9 Correct 630 ms 71764 KB Output is correct
10 Correct 471 ms 75180 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31064 KB Output is correct
2 Correct 5 ms 31324 KB Output is correct
3 Correct 5 ms 31324 KB Output is correct
4 Correct 4 ms 31192 KB Output is correct
5 Correct 5 ms 31324 KB Output is correct
6 Correct 5 ms 31580 KB Output is correct
7 Correct 4 ms 31068 KB Output is correct
8 Correct 5 ms 31324 KB Output is correct
9 Correct 5 ms 31324 KB Output is correct
10 Correct 8 ms 31324 KB Output is correct
11 Incorrect 8 ms 31320 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31064 KB Output is correct
2 Correct 5 ms 31324 KB Output is correct
3 Correct 5 ms 31324 KB Output is correct
4 Correct 4 ms 31192 KB Output is correct
5 Correct 5 ms 31324 KB Output is correct
6 Correct 5 ms 31580 KB Output is correct
7 Correct 4 ms 31068 KB Output is correct
8 Correct 5 ms 31324 KB Output is correct
9 Correct 5 ms 31324 KB Output is correct
10 Correct 8 ms 31324 KB Output is correct
11 Incorrect 8 ms 31320 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31064 KB Output is correct
2 Correct 5 ms 31324 KB Output is correct
3 Correct 5 ms 31324 KB Output is correct
4 Correct 4 ms 31192 KB Output is correct
5 Correct 5 ms 31324 KB Output is correct
6 Correct 5 ms 31580 KB Output is correct
7 Correct 4 ms 31068 KB Output is correct
8 Correct 5 ms 31324 KB Output is correct
9 Correct 5 ms 31324 KB Output is correct
10 Correct 8 ms 31324 KB Output is correct
11 Correct 266 ms 54052 KB Output is correct
12 Correct 493 ms 64084 KB Output is correct
13 Correct 545 ms 84816 KB Output is correct
14 Correct 632 ms 71504 KB Output is correct
15 Correct 676 ms 72384 KB Output is correct
16 Correct 662 ms 107860 KB Output is correct
17 Correct 497 ms 82256 KB Output is correct
18 Correct 604 ms 68688 KB Output is correct
19 Correct 630 ms 71764 KB Output is correct
20 Correct 471 ms 75180 KB Output is correct
21 Incorrect 8 ms 31320 KB Output isn't correct
22 Halted 0 ms 0 KB -