oj.uz

Submission #1037100

# Submission time Handle Problem Language Result Execution time Memory
1037100 2024-07-28T04:45:36 Z 8pete8 Parachute rings (IOI12_rings) C++17
37 / 100
 719 ms 120692 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,valid[mxn+10],on[mxn+10];
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(){
  cnt=0;
  int mx=0;
  for(int i=0;i<n;i++)add[i]=0,on[i]=0,vis[i]=0;
  for(int i=0;i<n;i++){
    if(!vis[i])dfs(i,-1);
    mx=max(mx,add[i]);
  }
  if(cnt>1)return 0;//atmost 1 comp with cycle
  int node=-1,have=0;
  for(int i=0;i<n;i++)if(adj[i].size()>=3)have++;
  int 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(){
      |                   ^
rings.cpp: In function 'int CountCritical()':
rings.cpp:64:7: warning: unused variable 'node' [-Wunused-variable]
   64 |   int node=-1,have=0;
      |       ^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29020 KB Output is correct
2 Correct 5 ms 29276 KB Output is correct
3 Correct 5 ms 29524 KB Output is correct
4 Correct 4 ms 29232 KB Output is correct
5 Correct 5 ms 29276 KB Output is correct
6 Correct 6 ms 29532 KB Output is correct
7 Correct 4 ms 29016 KB Output is correct
8 Correct 5 ms 29276 KB Output is correct
9 Correct 6 ms 29532 KB Output is correct
10 Correct 5 ms 29276 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 58504 KB Output is correct
2 Correct 513 ms 74580 KB Output is correct
3 Correct 564 ms 99344 KB Output is correct
4 Correct 716 ms 84744 KB Output is correct
5 Correct 688 ms 85584 KB Output is correct
6 Correct 680 ms 120692 KB Output is correct
7 Correct 493 ms 96300 KB Output is correct
8 Correct 637 ms 81236 KB Output is correct
9 Correct 719 ms 85004 KB Output is correct
10 Correct 500 ms 87584 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29020 KB Output is correct
2 Correct 5 ms 29276 KB Output is correct
3 Correct 5 ms 29524 KB Output is correct
4 Correct 4 ms 29232 KB Output is correct
5 Correct 5 ms 29276 KB Output is correct
6 Correct 6 ms 29532 KB Output is correct
7 Correct 4 ms 29016 KB Output is correct
8 Correct 5 ms 29276 KB Output is correct
9 Correct 6 ms 29532 KB Output is correct
10 Correct 5 ms 29276 KB Output is correct
11 Incorrect 9 ms 29276 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 29020 KB Output is correct
2 Correct 5 ms 29276 KB Output is correct
3 Correct 5 ms 29524 KB Output is correct
4 Correct 4 ms 29232 KB Output is correct
5 Correct 5 ms 29276 KB Output is correct
6 Correct 6 ms 29532 KB Output is correct
7 Correct 4 ms 29016 KB Output is correct
8 Correct 5 ms 29276 KB Output is correct
9 Correct 6 ms 29532 KB Output is correct
10 Correct 5 ms 29276 KB Output is correct
11 Incorrect 9 ms 29276 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 29020 KB Output is correct
2 Correct 5 ms 29276 KB Output is correct
3 Correct 5 ms 29524 KB Output is correct
4 Correct 4 ms 29232 KB Output is correct
5 Correct 5 ms 29276 KB Output is correct
6 Correct 6 ms 29532 KB Output is correct
7 Correct 4 ms 29016 KB Output is correct
8 Correct 5 ms 29276 KB Output is correct
9 Correct 6 ms 29532 KB Output is correct
10 Correct 5 ms 29276 KB Output is correct
11 Correct 225 ms 58504 KB Output is correct
12 Correct 513 ms 74580 KB Output is correct
13 Correct 564 ms 99344 KB Output is correct
14 Correct 716 ms 84744 KB Output is correct
15 Correct 688 ms 85584 KB Output is correct
16 Correct 680 ms 120692 KB Output is correct
17 Correct 493 ms 96300 KB Output is correct
18 Correct 637 ms 81236 KB Output is correct
19 Correct 719 ms 85004 KB Output is correct
20 Correct 500 ms 87584 KB Output is correct
21 Incorrect 9 ms 29276 KB Output isn't correct
22 Halted 0 ms 0 KB -