Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- weak weak we ak we akwea weak we
- weak weak we ak weak weak we ak we
- weakweak we ak wea ak we akwe
- wea we ak we ak we akwe
- wea we ak we ak we akwe
- wea eak weak we ak we ak we
- wea wea ak we ak weak we
- we
- we ak wea ak weak we
- we ak wea weak wea eak we
- we ak we ak wea wea we we
- weak we ak we we we we
- we we ak we we we we
- we wea weak wea wea weak weak
- weak wea akw weak weak
- */
- using namespace std;
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <cmath>
- #include <utility>
- #include <bitset>
- #include <set>
- #include <string>
- #include <stack>
- #include <iomanip>
- #include <map>
- #include <memory.h>
- #include <deque>
- #define pb push_back
- #define pii pair<int,int>
- #define F first
- #define S second
- #define LL long long
- #define mid (LB+RB)/2
- #define vvl vector <vector<LL>>
- #define vl vector <LL>
- #define mkp make_pair
- //iterators
- #define iter(x) x.begin(),x.end()
- #define aiter(a,n) a,a+n
- //loops
- #define REP(n) for (int ___=n;___--;)
- #define REP0(i,n) for (int i=0;i<n;++i)
- #define REP1(i,n) for (int i=1;i<=n;++i)
- #define FOR(i,b,l,k) for (int i=b;i!=l;i+=k)
- #define forEach(i,v) for (auto i:v)
- /*
- yungyao so weeeeeeeeeeeeeeeeeeeeeeeeeeak
- 8e7 so dian
- FHVirus so dian
- youou so dian
- KYW so dian
- hubert so dian
- jass so dian
- tingyu so dian
- panda so dian
- */
- //IO
- #include <iostream>
- #define theyRSOOOOOOOOODIAN ios_base::sync_with_stdio(false),cin.tie(0);
- //testing some stuff, still under construction
- //a lot more useful while debug
- inline void print(vector <int> v){
- for (auto i:v)
- cout << i << ' ';
- cout << '\n';
- }
- inline void print(vector <int> v,char sep,char end){
- for (auto i:v)
- cout << i << sep;
- cout << end;
- }
- //constants
- const LL maxn = 100100,mod = 0;
- //workspace
- bool mat[530][maxn];
- inline void solve(){
- int n,m;
- vector <int> graph[maxn];
- int h_to_mat[maxn];
- cin >> n >> m;
- const int split = sqrt(m);
- vector <pii> edge(m);
- while (m--){
- int u,v;
- cin >> u >> v;
- edge[m] = mkp(u,v);
- graph[u].pb(v); graph[v].pb(u);
- }
- int heavy_cnt = 0;
- REP0(i,n){
- if (graph[i].size() > split){
- for (auto j:graph[i])
- mat[heavy_cnt][j] = true;
- h_to_mat[i] = heavy_cnt++;
- }
- else
- sort (iter(graph[i]));
- }
- int cnt = 0;
- for (auto [u,v]:edge){
- if (graph[u].size() < graph[v].size())
- swap(u,v);
- if (graph[u].size() > split){
- int i = h_to_mat[u];
- for (auto j:graph[v])
- cnt += mat[i][j];
- }
- else{
- for (int i=0,j=0;j<graph[v].size();++j){
- while (graph[u][i] < graph[v][j] && i + 1 < graph[u].size())
- ++i;
- cnt += u != graph[u][i] && graph[u][i] == graph[v][j];
- }
- }
- }
- cout << cnt / 3 << '\n';
- }
- int main(){
- theyRSOOOOOOOOODIAN
- //for (int ;cin;)//use in multi-testcases and end in EOF problems
- //int t,i=1;for (cin >> t;i<=t;++i)//use in multi-testcases problems
- //cout << "Case #" << i << ": ",//use in Google, FB competitions
- solve();//always used
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement