| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 829890 |
2023-08-18T15:36:34 Z |
tolbi |
Duathlon (APIO18_duathlon) |
C++17 |
|
1000 ms |
28108 KB |
#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define tol(bi) (1LL<<((int)(bi)))
#define endl '\n'
typedef long long ll;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
ll solve(int n, vector<int> u, vector<int> v){
int totn = n;
vector<vector<int>> arr(n);
for (int i = 0; i < u.size(); i++){
arr[u[i]].push_back(v[i]);
arr[v[i]].push_back(u[i]);
}
vector<int> dept(n,-1);
vector<int> ele(n);
vector<int> sz;
vector<vector<int>> hehe;
function<int(int,int)> f;
function<pair<int,vector<int>>(int,int)> f2;
vector<int> par(n);
f2 = [&](int node, int lnode)->pair<int,vector<int>>{
vector<int> stk;
if (lnode!=-1) par[node]=lnode;
if (lnode!=-1) dept[node]=dept[lnode]+1;
int mide = dept[node];
for (int i = 0; i < arr[node].size(); i++){
if (dept[arr[node][i]]!=-1){
mide=min(mide,dept[arr[node][i]]);
continue;
}
pair<int,vector<int>> hueh = f2(arr[node][i],node);
mide=min(mide,hueh.first);
while (hueh.second.size()){
stk.push_back(hueh.second.back());
hueh.second.pop_back();
}
}
stk.push_back(node);
if (mide==dept[node]){
sz.push_back(0);
while (stk.size()){
ele[stk.back()]=hehe.size();
stk.pop_back();
sz.back()++;
}
hehe.push_back(vector<int>());
}
return {mide,stk};
};
dept[0]=0;
f2(0,-1);
for (int i = 1; i < n; i++){
if (ele[i]!=ele[par[i]]){
hehe[ele[i]].push_back(ele[par[i]]);
hehe[ele[par[i]]].push_back(ele[i]);
}
}
n=hehe.size();
dept[0]=0;
swap(arr,hehe);
ll ans = 0;
for (int i = 0; i < sz.size(); i++){
ans+=(ll)sz[i]*((ll)sz[i]-1)*((ll)sz[i]-2);
}//3 from cycle
vector<int> subsz(n);
//coutarr(sz);
f = [&](int node, int lnode)->int{
subsz[node]=sz[node];
for (int i = 0; i < arr[node].size(); i++){
if (arr[node][i]==lnode) continue;
f(arr[node][i],node);
subsz[node]+=subsz[arr[node][i]];
ans+=((ll)subsz[arr[node][i]])*((ll)sz[node])*((ll)totn-subsz[arr[node][i]]-sz[node]);
//2 from outside, 1 from cycle
ans+=(ll)(sz[node]-1)*((ll)sz[node]-1)*(ll)subsz[arr[node][i]]*2LL;
//2 from cycle, 1 from outside
}
ans+=(ll)(sz[node]-1)*((ll)sz[node]-1)*((ll)totn-subsz[node])*2LL;
ans+=(ll)(sz[node])*((ll)totn-subsz[node])*((ll)subsz[node]-(ll)sz[node]);
return 23;
};
f(0,-1);
return ans;
}
int32_t main(){
int T = 1;
int tno = 0;
while (T-(tno++)){
deci(n);deci(m);
vector<int> par(n);
iota(par.begin(), par.end(), 0);
function<int(int)> find;
find = [&](int node)->int{
if (par[node]==node) return node;
return par[node]=find(par[node]);
};
vector<pair<int,int>> edges(m);
for (int i = 0; i < m; i++){
cin>>edges[i].first>>edges[i].second;
edges[i].first--,edges[i].second--;
int u = edges[i].first;
int v = edges[i].second;
u=find(u);
v=find(v);
if (ayahya()%2) swap(u,v);
par[u]=v;
}
map<int,int> mp;
map<int,vector<int>> u;
map<int,vector<int>> v;
vector<int> indis(n);
for (int i = 0; i < n; i++){
indis[i]=mp[find(i)]++;
}
for (int i = 0; i < m; i++){
u[find(edges[i].first)].push_back(indis[edges[i].first]);
v[find(edges[i].first)].push_back(indis[edges[i].second]);
}
ll ans = 0;
for (auto it : mp){
ans+=solve(it.second,u[it.first],v[it.first]);
u.erase(it.first);
v.erase(it.first);
}
cout<<ans<<endl;
}
}
Compilation message
count_triplets.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
1 | #pragma optimize("Bismillahirrahmanirrahim")
|
count_triplets.cpp: In function 'll solve(int, std::vector<int>, std::vector<int>)':
count_triplets.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for (int i = 0; i < u.size(); i++){
| ~~^~~~~~~~~~
count_triplets.cpp: In lambda function:
count_triplets.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (int i = 0; i < arr[node].size(); i++){
| ~~^~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'll solve(int, std::vector<int>, std::vector<int>)':
count_triplets.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int i = 0; i < sz.size(); i++){
| ~~^~~~~~~~~~~
count_triplets.cpp: In lambda function:
count_triplets.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for (int i = 0; i < arr[node].size(); i++){
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
304 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
304 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1066 ms |
28108 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
11932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
11568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
304 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
304 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
