oj.uz

Submission #1037103

# Submission time Handle Problem Language Result Execution time Memory
1037103 2024-07-28T05:10:50 Z 8pete8 Parachute rings (IOI12_rings) C++17
37 / 100
 694 ms 107856 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 ans;
void Init(int N_) {
  n=N_;
}
void Link(int a,int b){
  adj[a].pb(b);
  adj[b].pb(a);
}
int add[mxn+10],rem[mxn+10],cnt=0,on[mxn+10],cnt2=0;
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(){
  cnt2=0;
  int mx=0;
  for(int i=0;i<n;i++)add[i]=0,on[i]=0,vis[i]=0,rem[i]=0;
  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++;
  }
  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:17: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   38 | void Init(int N_) {
      |                 ^
rings.cpp:41:22: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   41 | void Link(int a,int b){
      |                      ^
rings.cpp:46:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   46 | void dfs(int cur,int p){
      |                       ^
rings.cpp:55:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   55 | int CountCritical(){
      |                   ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31068 KB Output is correct
2 Correct 5 ms 31324 KB Output is correct
3 Correct 5 ms 31324 KB Output is correct
4 Correct 5 ms 31068 KB Output is correct
5 Correct 5 ms 31320 KB Output is correct
6 Correct 5 ms 31580 KB Output is correct
7 Correct 6 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 222 ms 53844 KB Output is correct
2 Correct 502 ms 64088 KB Output is correct
3 Correct 587 ms 84732 KB Output is correct
4 Correct 693 ms 71504 KB Output is correct
5 Correct 669 ms 72272 KB Output is correct
6 Correct 678 ms 107856 KB Output is correct
7 Correct 558 ms 82512 KB Output is correct
8 Correct 630 ms 68864 KB Output is correct
9 Correct 694 ms 71764 KB Output is correct
10 Correct 477 ms 75092 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31068 KB Output is correct
2 Correct 5 ms 31324 KB Output is correct
3 Correct 5 ms 31324 KB Output is correct
4 Correct 5 ms 31068 KB Output is correct
5 Correct 5 ms 31320 KB Output is correct
6 Correct 5 ms 31580 KB Output is correct
7 Correct 6 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 9 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 5 ms 31068 KB Output is correct
2 Correct 5 ms 31324 KB Output is correct
3 Correct 5 ms 31324 KB Output is correct
4 Correct 5 ms 31068 KB Output is correct
5 Correct 5 ms 31320 KB Output is correct
6 Correct 5 ms 31580 KB Output is correct
7 Correct 6 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 9 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 5 ms 31068 KB Output is correct
2 Correct 5 ms 31324 KB Output is correct
3 Correct 5 ms 31324 KB Output is correct
4 Correct 5 ms 31068 KB Output is correct
5 Correct 5 ms 31320 KB Output is correct
6 Correct 5 ms 31580 KB Output is correct
7 Correct 6 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 222 ms 53844 KB Output is correct
12 Correct 502 ms 64088 KB Output is correct
13 Correct 587 ms 84732 KB Output is correct
14 Correct 693 ms 71504 KB Output is correct
15 Correct 669 ms 72272 KB Output is correct
16 Correct 678 ms 107856 KB Output is correct
17 Correct 558 ms 82512 KB Output is correct
18 Correct 630 ms 68864 KB Output is correct
19 Correct 694 ms 71764 KB Output is correct
20 Correct 477 ms 75092 KB Output is correct
21 Incorrect 9 ms 31320 KB Output isn't correct
22 Halted 0 ms 0 KB -