Submission #300916

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
300916	2020-09-17T15:05:08 Z	Theo830	Connecting Supertrees (IOI20_supertrees)	C++17	Compilation error	0 ms	0 KB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
typedef int ll;
ll INF = 1e9+7;
ll MOD = 998244353;
typedef pair<long long,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define rf(i,a,b) for(long long i=a;i>=b;i--)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define w(t) while(t--)
#define c(n); cin>>n;
#define p(n) cout<<n;
#define pl(n) cout<<n<<"\n";
#define ps(n); cout<<n<<" ";
#define F first
#define S second
#define pb(a) push_back(a)
#define all(x) (x).begin(), (x).end()
#define ull unsigned long long
#define vll vector<ll>
#define vii vector<ii>
#define mkp make_pair
#define ld long double
#define arrin(a,n) f(i,0,n){cin>>a[i];}
#define arrout(a,n) f(i,0,n){cout<<a[i]<<" ";}
#define printclock cerr<<"Time : "<<*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define PI (2*acos(0))
#define EPS 1e-18
const long long N = 2e5+5;
const long long M = 1e6+5;
vll visit,dist,taken;
vector<vll> adj,ad;
vector<vii> adj2;
priority_queue<ii,vector<ii>, greater<ii> > pq;
ll bit[N]={0};
ll par[N]={0};
ll an[N][35];
ll depth[N]={0};
ll siz;
ll res = 0;
ll mycbrt(ll num){ll l = 1,r = 1000000;ll ans = 0;while(l <= r){ll mid = (l+r)/2;if(mid * mid * mid <= num){l = mid + 1;ans = max(ans,mid);}else{r = mid - 1;}}return ans;}
ll lcm(ll a,ll b){return (a * b) / __gcd(a,b);}
ll gcd(ll a,ll b){return __gcd(a,b);}
ll power(ll a,ll b,ll MOD){if(b == 0)return 1;if(b == 1)return a;ll ans = power(a,b/2,MOD) % MOD;ans *= ans;ans %= MOD;if(b % 2 == 1)ans *= a;return ans%MOD;}
ll inverse(ll x){x%=MOD;return power(x,MOD-2,MOD);}
void BITup(ll k, ll x){while(k <= siz){bit[k]+=x;k += k & -k;}}
ll BITq(ll k){ll s=0;while(k>=1){s+=bit[k];k -= k &-k;}return s;}
struct point{ll x,y,idx;};
void dfs(ll v){visit[v] = 1;for(auto x:ad[v]){if(!visit[x]){depth[x] = depth[v] + 1;dfs(x);}}}
void bfs(ll s){visit[s] = 1;queue<ll>q;q.push(s);while(!q.empty()){ll u = q.front();ps(u);q.pop();for(auto x:adj[u]){if(!visit[x]){visit[x] = 1;q.push(x);}}}}
void dijkstra(ll s){pq.push(ii(0,s));dist[s] = 0;while(!pq.empty()){ii f = pq.top();pq.pop();ll w = f.F;ll u = f.S;if(w > dist[u]){continue;}for(auto v:adj2[u]){if(dist[u] + v.S < dist[v.F]){dist[v.F] = dist[u] + v.S;pq.push(ii(dist[v.F],v.F));}}}}
void prim(ll edge) {taken[edge] = 1;for(auto v:adj2[edge]) {if (taken[v.first]==0)pq.push(ii(v.second, v.first));}}
ll mst(ll s){taken.assign(N, 0);prim(s);ll cost = 0;while(!pq.empty()){ii front = pq.top();pq.pop();ll w = front.first;ll u = front.second;if(taken[u]==0)cost += w;prim(u);}return cost;}
void bfs01(ll s){deque<ll>q;dist[s] = 0;q.push_back(s);while(!q.empty()){ll v = q.front();q.pop_front();for(auto x:adj2[v]){if(dist[x.F] > dist[v] + x.S){dist[x.F] = dist[v] + x.S;if(x.S == 0){q.push_front(x.F);}else{q.push_back(x.F);}}}}}
void build(ll s,ll p){an[s][0] = p;f(i,1,35){an[s][i] = an[an[s][i-1]][i-1];}for(auto x:adj[s]){if(x != p){depth[x] = depth[s] + 1;build(x,s);}}}
ll kth(ll x,ll k){ll ans = x;if(depth[x] < k){return -1;}ll pos = 0;while(k > 0){if(k % 2){ans = an[ans][pos];}pos++;k /= 2;}return ans;}
ll lca(ll a,ll b){if(depth[a] > depth[b]){swap(a,b);}b = kth(b,abs(depth[a] - depth[b]));if(a == b){return a;}for(ll i = 34;i >= 0;i--){if(an[a][i] == an[b][i]){continue;}a = an[a][i];b = an[b][i];}return an[a][0];}
ll find_dsu(ll x){if(par[x] == x){return x;}par[x] = find_dsu(par[x]);return par[x];}
void union_dsu(ll x,ll y){ll pos1 = find_dsu(x);ll pos2 = find_dsu(y);par[pos2] = pos1;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ll> distr;
ll rnd(ll a, ll b){return distr(rng)%(b-a+1)+a;}
void YESNO(ll a){if(!!a){pl("YES");}else{pl("NO");}}
void filesin(void){freopen("input.out","r",stdin);}
void filesout(void){freopen("tracing.out","w",stdout);}
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Training
set<ll>ev;
bool ok = 1;
ll comp[1005] = {0};
void solve(ll idx,ll s){
    ev.insert(idx);
    comp[idx] = s;
    for(auto x:adj[idx]){
        if(!ev.count(x)){
            solve(x,s);
        }
    }
}
vll exo;
void solvi(ll s){
    visit[s] = 1;
    exo.pb(s);
    for(auto x:ad[s]){
        if(!visit[x]){
            solvi(x);
        }
    }
}
int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> answer;
	for(int i = 0; i < n; i++) {
		vector<int> row;
		row.assign(n,0);
		answer.push_back(row);
	}
	adj.assign(n,vll());
	ad.assign(n,vll());
	f(i,0,n){
        f(j,0,n){
            if(p[i][j] >= 1){
                adj[i].pb(j);
            }
            if(p[i][j] == 1){
                ad[i].pb(j);
            }
            if(p[i][j] == 3){
                return 0;
            }
        }
	}
	ll c = 1;
	f(i,0,n){
        if(!ev.count(i)){
            solve(i,c);
            c++;
        }
	}
	f(i,0,n){
        f(j,0,n){
            if(p[i][j] == 0 && comp[i] == comp[j]){
                ok = 0;
            }
        }
	}
	if(ok){
        f(com,1,c){
            vll nodes,n2;
            f(i,0,n){
                if(comp[i] == com){
                    nodes.pb(i);
                }
            }
            visit.assign(n,0);
            for(auto x:nodes){
                if(!visit[x]){
                    exo.clear();
                    n2.pb(x);
                    solvi(x);
                    f(j,0,exo.size()-1){
                        ll pos = j+1;
                        answer[exo[j]][exo[pos]] = answer[exo[pos]][exo[j]] = 1;
                    }
                }
            }
            if(n2.size() == 2){
                ok = 0;
                return 0;
            }
            if(n2.size() != 1){
                f(i,0,n2.size()){
                    ll pos = n2[i],pos2 = n2[(i+1)%(n2.size())];
                    answer[pos][pos2] = answer[pos2][pos] = 1;
                }
            }
        }
	}
	if(ok == 0){
        return 0;
	}
	build(answer);
	return 1;
}

Compilation message

supertrees.cpp: In function 'void dfs(ll)':
supertrees.cpp:51:16: error: reference to 'visit' is ambiguous
   51 | void dfs(ll v){visit[v] = 1;for(auto x:ad[v]){if(!visit[x]){depth[x] = depth[v] + 1;dfs(x);}}}
      |                ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:133,
                 from supertrees.cpp:1:
/usr/include/c++/9/variant:1649:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1649 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
supertrees.cpp:33:5: note:                 'std::vector<int> visit'
   33 | vll visit,dist,taken;
      |     ^~~~~
supertrees.cpp:51:51: error: reference to 'visit' is ambiguous
   51 | void dfs(ll v){visit[v] = 1;for(auto x:ad[v]){if(!visit[x]){depth[x] = depth[v] + 1;dfs(x);}}}
      |                                                   ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:133,
                 from supertrees.cpp:1:
/usr/include/c++/9/variant:1649:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1649 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
supertrees.cpp:33:5: note:                 'std::vector<int> visit'
   33 | vll visit,dist,taken;
      |     ^~~~~
supertrees.cpp: In function 'void bfs(ll)':
supertrees.cpp:52:16: error: reference to 'visit' is ambiguous
   52 | void bfs(ll s){visit[s] = 1;queue<ll>q;q.push(s);while(!q.empty()){ll u = q.front();ps(u);q.pop();for(auto x:adj[u]){if(!visit[x]){visit[x] = 1;q.push(x);}}}}
      |                ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:133,
                 from supertrees.cpp:1:
/usr/include/c++/9/variant:1649:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1649 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
supertrees.cpp:33:5: note:                 'std::vector<int> visit'
   33 | vll visit,dist,taken;
      |     ^~~~~
supertrees.cpp:52:122: error: reference to 'visit' is ambiguous
   52 | void bfs(ll s){visit[s] = 1;queue<ll>q;q.push(s);while(!q.empty()){ll u = q.front();ps(u);q.pop();for(auto x:adj[u]){if(!visit[x]){visit[x] = 1;q.push(x);}}}}
      |                                                                                                                          ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:133,
                 from supertrees.cpp:1:
/usr/include/c++/9/variant:1649:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1649 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
supertrees.cpp:33:5: note:                 'std::vector<int> visit'
   33 | vll visit,dist,taken;
      |     ^~~~~
supertrees.cpp:52:132: error: reference to 'visit' is ambiguous
   52 | void bfs(ll s){visit[s] = 1;queue<ll>q;q.push(s);while(!q.empty()){ll u = q.front();ps(u);q.pop();for(auto x:adj[u]){if(!visit[x]){visit[x] = 1;q.push(x);}}}}
      |                                                                                                                                    ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:133,
                 from supertrees.cpp:1:
/usr/include/c++/9/variant:1649:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1649 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
supertrees.cpp:33:5: note:                 'std::vector<int> visit'
   33 | vll visit,dist,taken;
      |     ^~~~~
supertrees.cpp: In function 'void solvi(ll)':
supertrees.cpp:88:5: error: reference to 'visit' is ambiguous
   88 |     visit[s] = 1;
      |     ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:133,
                 from supertrees.cpp:1:
/usr/include/c++/9/variant:1649:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1649 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
supertrees.cpp:33:5: note:                 'std::vector<int> visit'
   33 | vll visit,dist,taken;
      |     ^~~~~
supertrees.cpp:91:13: error: reference to 'visit' is ambiguous
   91 |         if(!visit[x]){
      |             ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:133,
                 from supertrees.cpp:1:
/usr/include/c++/9/variant:1649:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1649 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
supertrees.cpp:33:5: note:                 'std::vector<int> visit'
   33 | vll visit,dist,taken;
      |     ^~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:141:13: error: reference to 'visit' is ambiguous
  141 |             visit.assign(n,0);
      |             ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:133,
                 from supertrees.cpp:1:
/usr/include/c++/9/variant:1649:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1649 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
supertrees.cpp:33:5: note:                 'std::vector<int> visit'
   33 | vll visit,dist,taken;
      |     ^~~~~
supertrees.cpp:143:21: error: reference to 'visit' is ambiguous
  143 |                 if(!visit[x]){
      |                     ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:133,
                 from supertrees.cpp:1:
/usr/include/c++/9/variant:1649:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1649 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
supertrees.cpp:33:5: note:                 'std::vector<int> visit'
   33 | vll visit,dist,taken;
      |     ^~~~~
supertrees.cpp:9:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f(i,a,b) for(ll i = a;i < b;i++)
......
  147 |                     f(j,0,exo.size()-1){
      |                       ~~~~~~~~~~~~~~~~
supertrees.cpp:147:21: note: in expansion of macro 'f'
  147 |                     f(j,0,exo.size()-1){
      |                     ^
supertrees.cpp:9:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f(i,a,b) for(ll i = a;i < b;i++)
......
  158 |                 f(i,0,n2.size()){
      |                   ~~~~~~~~~~~~~  
supertrees.cpp:158:17: note: in expansion of macro 'f'
  158 |                 f(i,0,n2.size()){
      |                 ^
supertrees.cpp: In function 'void filesin()':
supertrees.cpp:66:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   66 | void filesin(void){freopen("input.out","r",stdin);}
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp: In function 'void filesout()':
supertrees.cpp:67:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   67 | void filesout(void){freopen("tracing.out","w",stdout);}
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~