oj.uz

답안 #981477

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
981477 2024-05-13T09:10:35 Z vjudge1 철인 이종 경기 (APIO18_duathlon) C++17
31 / 100
 181 ms 37864 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 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

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 28620 KB Output is correct
2 Correct 51 ms 28504 KB Output is correct
3 Correct 98 ms 29268 KB Output is correct
4 Correct 77 ms 28792 KB Output is correct
5 Correct 78 ms 24440 KB Output is correct
6 Correct 104 ms 27728 KB Output is correct
7 Correct 110 ms 26708 KB Output is correct
8 Correct 110 ms 27728 KB Output is correct
9 Correct 112 ms 25168 KB Output is correct
10 Correct 89 ms 24912 KB Output is correct
11 Correct 87 ms 22100 KB Output is correct
12 Correct 86 ms 22072 KB Output is correct
13 Correct 78 ms 21992 KB Output is correct
14 Correct 74 ms 21496 KB Output is correct
15 Correct 64 ms 20848 KB Output is correct
16 Correct 61 ms 20308 KB Output is correct
17 Correct 4 ms 11356 KB Output is correct
18 Correct 4 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 11216 KB Output is correct
22 Correct 4 ms 11356 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 10076 KB Output is correct
2 Correct 3 ms 10076 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 3 ms 10076 KB Output is correct
9 Correct 3 ms 10076 KB Output is correct
10 Correct 4 ms 9920 KB Output is correct
11 Correct 3 ms 10076 KB Output is correct
12 Correct 3 ms 10076 KB Output is correct
13 Correct 3 ms 10076 KB Output is correct
14 Correct 3 ms 10108 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 10076 KB Output is correct
18 Correct 3 ms 10076 KB Output is correct
19 Correct 3 ms 10076 KB Output is correct
20 Correct 3 ms 10128 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 31412 KB Output is correct
2 Correct 168 ms 31408 KB Output is correct
3 Correct 151 ms 31216 KB Output is correct
4 Correct 149 ms 31312 KB Output is correct
5 Correct 148 ms 31260 KB Output is correct
6 Correct 152 ms 37864 KB Output is correct
7 Correct 176 ms 35920 KB Output is correct
8 Correct 181 ms 34640 KB Output is correct
9 Correct 158 ms 33360 KB Output is correct
10 Correct 145 ms 31312 KB Output is correct
11 Correct 157 ms 31312 KB Output is correct
12 Correct 159 ms 31472 KB Output is correct
13 Correct 151 ms 31316 KB Output is correct
14 Correct 131 ms 29572 KB Output is correct
15 Correct 118 ms 27932 KB Output is correct
16 Correct 70 ms 22352 KB Output is correct
17 Correct 151 ms 31564 KB Output is correct
18 Correct 149 ms 31552 KB Output is correct
19 Correct 158 ms 31648 KB Output is correct
20 Correct 144 ms 31688 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 10076 KB Output is correct
2 Correct 4 ms 10076 KB Output is correct
3 Incorrect 3 ms 10072 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 31248 KB Output is correct
2 Correct 156 ms 31164 KB Output is correct
3 Incorrect 140 ms 27956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 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 -