oj.uz

Submission #981456

# Submission time Handle Problem Language Result Execution time Memory
981456 2024-05-13T08:32:23 Z shenfe1 Duathlon (APIO18_duathlon) C++17
8 / 100
 125 ms 29784 KB 
#include <bits/stdc++.h>
 
#pragma optimize("Ofast")
#pragma target("avx2")
 
using namespace std;
 
#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define y1 yy
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define gcd(a,b) __gcd(a,b)
#define in insert
#define int ll

const int MAX=1e5+15;
const int B=300;
const int N=104;
const int block=400;
const int maxB=MAX/B+10;
const ll inf=2e18;  
const int mod=998244353;
const int mod1=1e9+9;
const ld eps=1e-9;
 
int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};
 
int binpow(int a,int n){
  if(!n)return 1;
  if(n%2==1)return a*binpow(a,n-1)%mod;
  int k=binpow(a,n/2);
  return k*k%mod;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,m;
vector<int> g[MAX];
int use[MAX];
int tin[MAX],fup[MAX],timer;
map<pii,int> br;
int cnt=0;
bool was;

void dfs(int v,int p=-1){
  tin[v]=fup[v]=++timer;
  use[v]=1;
  cnt++;
  for(auto to:g[v]){
    if(to==p)continue;
    if(!use[to]){
      dfs(to,v);
      fup[v]=min(fup[v],fup[to]);
      if(fup[to]>tin[v]){
        was=1;
        br[{v,to}]=br[{to,v}]=1;
      }
    }
    else{
      fup[v]=min(fup[v],tin[to]);
    }
  }
}

struct DSU{
  int f[MAX];

  void init(int n){
    for(int i=1;i<=n;i++){
      f[i]=i;
    }
  }

  int get(int v){
    if(f[v]==v)return v;
    return f[v]=get(f[v]);
  }

  void unite(int a,int b){
    a=get(a);
    b=get(b);
    if(rng()%2)swap(a,b);
    f[a]=b;
  }
}D;

int s[MAX];
int S[MAX];
int pr[MAX];
int PR[MAX];
vector<int> g1[MAX];

void dfs1(int v,int st,int p=-1){
  pr[v]=p;
  PR[v]=st;
  use[v]=1;
  sort(all(g1[v]));
  g1[v].erase(unique(all(g1[v])),g1[v].end());
  S[v]=s[v];
  for(auto to:g1[v]){
    if(to==p)continue;
    dfs1(to,st,v);
    S[v]+=S[to];
  }
}

void solve(){
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    int a,b;
    cin>>a>>b;
    g[a].pb(b);
    g[b].pb(a);
  }
  int ans=0;
  for(int i=1;i<=n;i++){
    if(!use[i]){
      dfs(i);
      if(was)ans+=cnt*(cnt-1)*(cnt-2)/3;
      else ans+=cnt*(cnt-1)*(cnt-2);
      cnt=0;
      was=0;
    }
  }
  cout<<ans<<"\n";
  return;
  D.init(n);
  for(int i=1;i<=n;i++){
    for(auto to:g[i]){
      if(!br.count({i,to})){
        D.unite(i,to);
      }
    }
  }
  for(int i=1;i<=n;i++){
    s[D.get(i)]++;
    for(auto to:g[i]){
      if(D.get(i)!=D.get(to)){
        g1[D.get(i)].pb(D.get(to));
      }
    }
  }
  // cerr<<"Ok\n";
  mem(use,0);
  for(int i=1;i<=n;i++){
    if(!use[D.get(i)]){
      dfs1(D.get(i),D.get(i));
    }
  }
  for(int i=1;i<=n;i++){
    if(D.get(i)==i){
      ans+=s[i]*(s[i]-1)*(s[i]-2)/6;
      int up=S[PR[i]]-S[i];
      int down=S[i]-s[i];
      ans+=s[i]*up*down;
      ans+=s[i]*(s[i]-1)*(S[PR[i]]-s[i]);
      for(auto to:g1[i]){
        if(to==pr[i])continue;
        ans+=S[to]*s[i]*(S[i]-S[to]-s[i]);
      }
    }
  }
  cout<<ans*2<<"\n";
}
 
signed main(){
  //  freopen("help.in","r",stdin);
  //  freopen("help.out","w",stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  // prec();
  int t=1;
  // cin>>t;
  while(t--)solve();
}

Compilation message

count_triplets.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("Ofast")
      | 
count_triplets.cpp:4: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    4 | #pragma target("avx2")
      |

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 2 ms 9372 KB Output is correct
4 Correct 2 ms 9308 KB Output is correct
5 Correct 2 ms 9308 KB Output is correct
6 Correct 2 ms 9304 KB Output is correct
7 Incorrect 2 ms 9308 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 2 ms 9372 KB Output is correct
4 Correct 2 ms 9308 KB Output is correct
5 Correct 2 ms 9308 KB Output is correct
6 Correct 2 ms 9304 KB Output is correct
7 Incorrect 2 ms 9308 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 28408 KB Output is correct
2 Correct 44 ms 29784 KB Output is correct
3 Correct 72 ms 29008 KB Output is correct
4 Correct 66 ms 29356 KB Output is correct
5 Correct 61 ms 24660 KB Output is correct
6 Correct 79 ms 27384 KB Output is correct
7 Correct 79 ms 25940 KB Output is correct
8 Correct 98 ms 27216 KB Output is correct
9 Correct 76 ms 24732 KB Output is correct
10 Correct 61 ms 24656 KB Output is correct
11 Correct 53 ms 20312 KB Output is correct
12 Correct 51 ms 20308 KB Output is correct
13 Correct 46 ms 20052 KB Output is correct
14 Correct 49 ms 19736 KB Output is correct
15 Correct 38 ms 18924 KB Output is correct
16 Correct 41 ms 18516 KB Output is correct
17 Correct 4 ms 11352 KB Output is correct
18 Correct 3 ms 11356 KB Output is correct
19 Correct 3 ms 11356 KB Output is correct
20 Correct 3 ms 11356 KB Output is correct
21 Correct 3 ms 11356 KB Output is correct
22 Correct 3 ms 11356 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 9564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 27476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 125 ms 27520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 2 ms 9372 KB Output is correct
4 Correct 2 ms 9308 KB Output is correct
5 Correct 2 ms 9308 KB Output is correct
6 Correct 2 ms 9304 KB Output is correct
7 Incorrect 2 ms 9308 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 2 ms 9372 KB Output is correct
4 Correct 2 ms 9308 KB Output is correct
5 Correct 2 ms 9308 KB Output is correct
6 Correct 2 ms 9304 KB Output is correct
7 Incorrect 2 ms 9308 KB Output isn't correct
8 Halted 0 ms 0 KB -