제출 #790327

#제출 시각아이디문제언어결과실행 시간메모리
790327LyricallyDuathlon (APIO18_duathlon)C++17
0 / 100
57 ms19664 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define pb push_back #define rep(i,n) for(int i=0;i<n;i++) #define rep1(i,n) for(int i=1;i<=n;i++) int read(){int x;scanf("%lld",&x);return x;} void print(int x){printf("%lld\n",x);} void file(string s) { freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } const int mod=998244353; int n,m; vector<int> edge[100005]; int deg[100005]; int Fa[100005]; vector<int> Set[100005]; int E[100005]; int Find(int x){return Fa[x]==x?x:Fa[x]=Find(Fa[x]);} void work() { int res=0; rep1(i,n) { if(!Set[i].empty()) { if(E[i]==Set[i].size()) { res+=E[i]*(E[i]-1)*(E[i]-2); } else { res+=(E[i]+1)*E[i]*(E[i]-1)/3; } } } print(res); } unordered_map<int,int> dpp[55][55]; bool e[55][55]; void dfs(int st,int x,int msk) { if(dpp[st][x].count(msk)){return;} dpp[st][x][msk]=1; for(int i:edge[x]) { if(msk&(1ll<<(i-1))){continue;} dfs(st,i,msk|(1ll<<(i-1))); } } //can we go from i to j with the path msk? void calc() { rep1(i,n) { for(int v:edge[i]) { e[i][v]=e[v][i]=1; } } rep1(i,n) { dfs(i,i,(1ll<<(i-1))); } int tot=0; rep1(i,n) { rep1(j,n) { if(i==j){continue;} if(Find(i)!=Find(j)){continue;} rep1(k,n) { if(i==k||j==k){continue;} if(Find(i)!=Find(k)){continue;} bool fl=0; for(auto it:dpp[i][k]) { for(auto nit:dpp[k][j]) { int x=it.first,y=nit.first; if(!((x-(1ll<<(k-1)))&y)) { fl=1;break; } } } tot+=fl; } } } print(tot); } bool vis[100005]; int res[100005]; int cnt[100005]; void dfs(int x,int fa) { cnt[x]=1; for(int v:edge[x]) { if(v==fa){continue;} dfs(v,x); cnt[x]+=cnt[v]; res[x]+=res[v]+cnt[v]; } } void dfs2(int x,int fa) { for(int v:edge[x]) { if(v==fa){continue;} res[v]=n-cnt[v]+res[x]-cnt[v]; dfs2(v,x); } } void solve() { int tot=0; rep1(i,n) { if(Set[i].empty()){continue;} dfs(i,0); /* for(auto v:Set[i]) { cout<<v<<" "<<cnt[v]<<" "<<res[v]<<endl; }*/ dfs2(i,0); /* for(auto v:Set[i]) { cout<<v<<" "<<cnt[v]<<" "<<res[v]<<endl; }*/ for(auto v:Set[i]) { tot+=res[v]-n+1; } } print(tot); } signed main() { n=read(),m=read();rep1(i,n){Fa[i]=i;} rep1(i,m) { int u=read(),v=read();Fa[Find(u)]=Find(v); edge[u].pb(v),edge[v].pb(u); deg[u]++,deg[v]++; } rep1(i,n) { Set[Find(i)].pb(i); } rep1(i,n) { for(auto v:edge[i]) { if(i>=v){continue;} E[Find(i)]++; } } bool fl=1; rep1(i,n) { if(Set[i].empty()){continue;} if(E[i]==(int)Set[i].size()-1){continue;} fl=0; } if(fl){solve();return 0;} bool f=1; rep1(i,n){f&=(deg[i]<=2);} if(f){work();return 0;} if(n<=10){calc();return 0;} return 0; }

컴파일 시 표준 에러 (stderr) 메시지

count_triplets.cpp: In function 'void work()':
count_triplets.cpp:30:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    if(E[i]==Set[i].size())
      |       ~~~~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'long long int read()':
count_triplets.cpp:8:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | int read(){int x;scanf("%lld",&x);return x;}
      |                  ~~~~~^~~~~~~~~~~
count_triplets.cpp: In function 'void file(std::string)':
count_triplets.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  freopen((s+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  freopen((s+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...