oj.uz

Submission #981476

# Submission time Handle Problem Language Result Execution time Memory
981476 2024-05-13T09:06:23 Z vjudge1 Duathlon (APIO18_duathlon) C++17
31 / 100
 206 ms 37716 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;

void dfs(int v,int p=-1){
  tin[v]=fup[v]=++timer;
  use[v]=1;
  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]){
        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);
  }
  for(int i=1;i<=n;i++){
    if(!use[i])dfs(i);
  }
  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));
    }
  }
  int ans=0;
  for(int i=1;i<=n;i++){
    if(D.get(i)==i){
      ans+=s[i]*(s[i]-1)*(s[i]-2);
      // cout<<s[i]*(s[i]-1)*(s[i]-2)<<"\n";
      int up=S[PR[i]]-S[i];
      int down=S[i]-s[i];
      ans+=2*s[i]*up*down;
      ans+=2*(s[i]-1)*(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<<"\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 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Incorrect 2 ms 9820 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 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Incorrect 2 ms 9820 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 51 ms 28500 KB Output is correct
2 Correct 51 ms 28508 KB Output is correct
3 Correct 97 ms 29364 KB Output is correct
4 Correct 91 ms 28968 KB Output is correct
5 Correct 78 ms 24204 KB Output is correct
6 Correct 100 ms 27752 KB Output is correct
7 Correct 111 ms 26708 KB Output is correct
8 Correct 145 ms 27732 KB Output is correct
9 Correct 104 ms 25292 KB Output is correct
10 Correct 91 ms 24996 KB Output is correct
11 Correct 79 ms 20820 KB Output is correct
12 Correct 77 ms 20820 KB Output is correct
13 Correct 74 ms 20820 KB Output is correct
14 Correct 73 ms 20564 KB Output is correct
15 Correct 56 ms 20052 KB Output is correct
16 Correct 70 ms 19420 KB Output is correct
17 Correct 6 ms 11356 KB Output is correct
18 Correct 6 ms 11356 KB Output is correct
19 Correct 4 ms 11356 KB Output is correct
20 Correct 4 ms 11356 KB Output is correct
21 Correct 4 ms 11352 KB Output is correct
22 Correct 4 ms 11356 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10044 KB Output is correct
2 Correct 3 ms 10328 KB Output is correct
3 Correct 3 ms 10076 KB Output is correct
4 Correct 3 ms 10076 KB Output is correct
5 Correct 3 ms 10076 KB Output is correct
6 Correct 3 ms 10076 KB Output is correct
7 Correct 3 ms 10076 KB Output is correct
8 Correct 4 ms 10324 KB Output is correct
9 Correct 3 ms 10076 KB Output is correct
10 Correct 3 ms 10132 KB Output is correct
11 Correct 3 ms 10076 KB Output is correct
12 Correct 4 ms 10076 KB Output is correct
13 Correct 3 ms 10076 KB Output is correct
14 Correct 3 ms 10076 KB Output is correct
15 Correct 3 ms 10076 KB Output is correct
16 Correct 3 ms 9820 KB Output is correct
17 Correct 3 ms 9920 KB Output is correct
18 Correct 3 ms 10076 KB Output is correct
19 Correct 3 ms 10084 KB Output is correct
20 Correct 3 ms 10076 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 31392 KB Output is correct
2 Correct 162 ms 31492 KB Output is correct
3 Correct 147 ms 31352 KB Output is correct
4 Correct 174 ms 31628 KB Output is correct
5 Correct 169 ms 31240 KB Output is correct
6 Correct 150 ms 37716 KB Output is correct
7 Correct 182 ms 35928 KB Output is correct
8 Correct 206 ms 34828 KB Output is correct
9 Correct 164 ms 33372 KB Output is correct
10 Correct 198 ms 31184 KB Output is correct
11 Correct 155 ms 31208 KB Output is correct
12 Correct 162 ms 31408 KB Output is correct
13 Correct 159 ms 31280 KB Output is correct
14 Correct 129 ms 29520 KB Output is correct
15 Correct 119 ms 27988 KB Output is correct
16 Correct 66 ms 22324 KB Output is correct
17 Correct 152 ms 31560 KB Output is correct
18 Correct 145 ms 31700 KB Output is correct
19 Correct 174 ms 31812 KB Output is correct
20 Correct 146 ms 31788 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10072 KB Output is correct
2 Correct 3 ms 10076 KB Output is correct
3 Incorrect 3 ms 10076 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 31508 KB Output is correct
2 Correct 156 ms 31060 KB Output is correct
3 Incorrect 145 ms 25996 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Incorrect 2 ms 9820 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 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Incorrect 2 ms 9820 KB Output isn't correct
8 Halted 0 ms 0 KB -