/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
#include "simurgh.h"
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
#define VV(vvvv,NNNN,xxxx); REP(i,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;
template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
class DSU //with range compression and union by subtree size
{
public:
ll N;
vector<ll> p,siz;
DSU(ll n)
{
N=n; REP(i,0,N) {p.pb(i); siz.pb(1);}
}
ll find(ll x)
{
if(p[x]==x) {return x;}
ll ans=find(p[x]);
p[x]=ans;
return ans;
}
void unionn(ll a, ll b)
{
a=find(a); b=find(b);
if(a==b) {return;}
if(siz[a]>siz[b]) {swap(a,b);}
p[a]=b; siz[b]+=siz[a];
}
vector<vector<ll> > EquivalenceClasses() //O(N)
{
vector<vector<ll> > rep; REP(i,0,N) {rep.pb({});}
REP(i,0,N) {rep[find(i)].pb(i);}
vector<vector<ll> > CC;
REP(i,0,N) {if(rep[i].size()>0) {CC.pb(rep[i]);}}
return CC;
}
};
class Graph
{
public:
ll N;
vector<vector<ll> > adj;
vector<ll> visited; //for DFS/BFS
vector<vector<ll> > dfs_tree;
Graph() {ll N=0LL;}
Graph(vector<vector<ll> > ad)
{
adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false);}
VV(dfs_tree,N,{});
}
void Reset()
{
REP(i,0,N) {visited[i]=false;}
}
void DFS_Tree(ll s)
{
if(visited[s]) {return;}
visited[s]=true;
REP(i,0,adj[s].size())
{
if(!visited[adj[s][i]]) {dfs_tree[s].pb(adj[s][i]); dfs_tree[adj[s][i]].pb(s); DFS_Tree(adj[s][i]);}
}
return;
}
};
vector<int> find_roads(int n, vector<int> u, vector<int> v)
{
ll N=(ll) n; ll M = u.size();
DSU D(N);
vector<ll> in; VV(in,M,-1); ll ed=0;
while(ed<N-1)
{
vector<vector<ll> > CC = D.EquivalenceClasses();
vector<ll> rep; VV(rep,N,-1); REP(i,0,CC.size()) {REP(j,0,CC[i].size()) {rep[CC[i][j]]=i;}}
vector<vector<ll> > adj; VV(adj,CC.size(),{});
map<pl,vector<ll> > m; ll a,b;
REP(i,0,M)
{
if(in[i]!=-1) {continue;}
a=rep[u[i]]; b=rep[v[i]];
if(m.find({a,b})==m.end()) {m[{a,b}]={}; m[{b,a}]={};}
m[{a,b}].pb(i); m[{b,a}].pb(i);
}
map<pl,vector<ll> >::iterator it=m.begin();
while(it!=m.end()) {adj[it->ff.ff].pb(it->ff.ss); it++;}
Graph G(adj); G.Reset(); G.DFS_Tree(0);
ll leaf=0; REP(i,0,G.N) {if(G.dfs_tree[i].size()<=1) {leaf=i; break;}}
vector<ll> c; REP(i,0,M) {if(in[i]==1) {c.pb(i);}}
ll nei;
REP(i,0,G.N)
{
if(i==leaf) {continue;}
REP(j,0,G.dfs_tree[i].size()) {nei=G.dfs_tree[i][j]; if(nei<i || nei==leaf) {continue;} c.pb(m[{i,nei}][0]);}
}
vector<pl> results; ll dummy;
REP(i,0,adj[leaf].size())
{
nei=adj[leaf][i];
REP(j,0,(m[{leaf,nei}].size()))
{
c.pb(m[{leaf,nei}][j]);
//DEBUG(0); REP(z,0,c.size()) {cout<<"("<<u[c[z]]<<","<<v[c[z]]<<") ";}cout<<endl;
dummy=count_common_roads(c);
results.pb({dummy,m[{leaf,nei}][j]});
c.pop_back();
}
}
sort(whole(results)); reverse(whole(results));
ll edgeindex;
REP(i,0,results.size())
{
edgeindex= results[i].ss;
if(results[i].ff==results[0].ff) {D.unionn(u[edgeindex],v[edgeindex]); in[edgeindex]=1; ed++;}
else {in[edgeindex]=0;}
}
}
vector<ll> c; REP(i,0,M) {if(in[i]==1) {c.pb(i);}}
return c;
}
Compilation message
simurgh.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
5 | #pragma GCC optimization ("O3")
|
simurgh.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
6 | #pragma GCC optimization ("unroll-loops")
|
simurgh.cpp: In constructor 'Graph::Graph()':
simurgh.cpp:94:17: warning: unused variable 'N' [-Wunused-variable]
94 | Graph() {ll N=0LL;}
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
correct |
| 2 |
Incorrect |
0 ms |
204 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
correct |
| 2 |
Incorrect |
0 ms |
204 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
correct |
| 2 |
Incorrect |
0 ms |
204 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
correct |
| 2 |
Incorrect |
1 ms |
204 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
correct |
| 2 |
Incorrect |
0 ms |
204 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
