oj.uz

Submission #1037101

# Submission time Handle Problem Language Result Execution time Memory
1037101 2024-07-28T04:46:58 Z 8pete8 Parachute rings (IOI12_rings) C++17
37 / 100
 685 ms 107740 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];
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,rem[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++;
  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 5 ms 31064 KB Output is correct
2 Correct 5 ms 31196 KB Output is correct
3 Correct 5 ms 31400 KB Output is correct
4 Correct 5 ms 31068 KB Output is correct
5 Correct 5 ms 31412 KB Output is correct
6 Correct 6 ms 31676 KB Output is correct
7 Correct 5 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 5 ms 31320 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 53844 KB Output is correct
2 Correct 524 ms 63956 KB Output is correct
3 Correct 570 ms 84820 KB Output is correct
4 Correct 685 ms 71504 KB Output is correct
5 Correct 651 ms 72276 KB Output is correct
6 Correct 658 ms 107740 KB Output is correct
7 Correct 509 ms 82516 KB Output is correct
8 Correct 619 ms 68612 KB Output is correct
9 Correct 660 ms 71760 KB Output is correct
10 Correct 493 ms 75092 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31064 KB Output is correct
2 Correct 5 ms 31196 KB Output is correct
3 Correct 5 ms 31400 KB Output is correct
4 Correct 5 ms 31068 KB Output is correct
5 Correct 5 ms 31412 KB Output is correct
6 Correct 6 ms 31676 KB Output is correct
7 Correct 5 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 5 ms 31320 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 31064 KB Output is correct
2 Correct 5 ms 31196 KB Output is correct
3 Correct 5 ms 31400 KB Output is correct
4 Correct 5 ms 31068 KB Output is correct
5 Correct 5 ms 31412 KB Output is correct
6 Correct 6 ms 31676 KB Output is correct
7 Correct 5 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 5 ms 31320 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 31064 KB Output is correct
2 Correct 5 ms 31196 KB Output is correct
3 Correct 5 ms 31400 KB Output is correct
4 Correct 5 ms 31068 KB Output is correct
5 Correct 5 ms 31412 KB Output is correct
6 Correct 6 ms 31676 KB Output is correct
7 Correct 5 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 5 ms 31320 KB Output is correct
11 Correct 234 ms 53844 KB Output is correct
12 Correct 524 ms 63956 KB Output is correct
13 Correct 570 ms 84820 KB Output is correct
14 Correct 685 ms 71504 KB Output is correct
15 Correct 651 ms 72276 KB Output is correct
16 Correct 658 ms 107740 KB Output is correct
17 Correct 509 ms 82516 KB Output is correct
18 Correct 619 ms 68612 KB Output is correct
19 Correct 660 ms 71760 KB Output is correct
20 Correct 493 ms 75092 KB Output is correct
21 Incorrect 9 ms 31320 KB Output isn't correct
22 Halted 0 ms 0 KB -