이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 2e5;
vector<int> g[nax];
int seg[4*nax],lazy[4*nax],fr[nax],to[nax],id[nax];
int T,n,m;
ll ans;
void pro(int n,int s,int e){
seg[n] += lazy[n];
if(s != e){
lazy[n*2] += lazy[n];
lazy[n*2+1] += lazy[n];
}
lazy[n] = 0;
}
void update(int n,int s,int e,int l,int r,int val){
pro(n,s,e);
if(s > r || e < l)
return;
if(s >= l && e <= r){
lazy[n] += val;
pro(n,s,e);
return;
}
update(n*2,s,(s+e)/2,l,r,val);
update(n*2+1,(s+e)/2+1,e,l,r,val);
seg[n] = seg[n*2] + seg[n*2+1];
}
ll get(int n,int s,int e,int l,int r){
pro(n,s,e);
if(s > r || e < l)
return 0;
if(s >= l && e <= r)
return seg[n];
return get(n*2,s,(s+e)/2,l,r) + get(n*2+1,(s+e)/2+1,e,l,r);
}
void dfs(int u,int p,int d){
id[u] = fr[u] = ++T;
update(1,1,n,T,T,d);
for(int v : g[u]){
if(v == p)
continue;
dfs(v,u,d+1);
}
to[u] = T;
}
void calc(int u,int p){
ans += get(1,1,n,1,n) - n + 1;
for(int v : g[u]){
if(v == p)
continue;
update(1,1,n,1,n,1);
update(1,1,n,fr[v],to[v],-2);
calc(v,u);
update(1,1,n,1,n,-1);
update(1,1,n,fr[v],to[v],2);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
if(n == m){
ans = n * (n-1) * (n-2);
}else if(n == m+1){
dfs(1,0,0);
calc(1,0);
}else assert(0);
printf("%lld\n", ans);
}
컴파일 시 표준 에러 (stderr) 메시지
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
~~~~~^~~~~~~~~~~~~~
count_triplets.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&u,&v);
~~~~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |