Submission #49983

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49983	2018-06-05T23:05:04 Z	Benq	Simurgh (IOI17_simurgh)	C++14	Compilation error	0 ms	0 KB

simurgh

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

// #include "simurgh.h"

vpi adj[500];
int comp[500];
vi tre[500], tmp[500], allComp;
int n;
int need[500*499/2], sec[500*499/2];
vi u,v, res;

template<int SZ> struct DSU {
    int par[SZ], sz[SZ];
    DSU() {
        F0R(i,SZ) par[i] = i, sz[i] = 1;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    
    bool unite(int x, int y) { // union-by-rank
    	x = get(x), y = get(y);
    	if (x == y) return 0;
    	if (sz[x] < sz[y]) swap(x,y);
    	sz[x] += sz[y], par[y] = x;
    	return 1;
    }
};

int co = 0;

/*int count_common_roads(vi z) {
    co ++;
    assert(sz(z) == n-1);
    DSU<500> D = DSU<500>();
    int ret = 0;
    for (int i: z) {
        if (!D.unite(u[i],v[i])) exit(5);
        if (sec[i]) ret ++;
    }
    return ret;
}*/

void test(int ind) {
    vpi bes;
    
    for (int x: tmp[ind]) {
        vi z = {x};
        for (int i: allComp) {
            if (i != ind && i > 0) z.pb(tmp[i].back());
            z.insert(z.end(),all(tre[i]));
        }
        bes.pb({count_common_roads(z),x});
    }
    
    sort(all(bes));
    for (auto a: bes) {
        if (a.f == bes.back().f) {
            // cout << "ZZ " << a.s << " " << sz(bes) << "\n";
            need[a.s] = 1;
            res.pb(a.s);
        } else need[a.s] = -1;
    }
}

void dfs(int x, int lab) {
    comp[x] = lab;
    for (auto a: adj[x]) if (comp[a.f] == -1) {
        tre[lab].pb(a.s);
        dfs(a.f,lab);
    }
}

void test() {
    res.clear();
    FOR(i,1,n) {
        tre[i].clear();
        tmp[i].clear();
    }
    
    allComp.clear();
    allComp.pb(0);
    
    F0R(i,n) if (comp[i] == -1) {
        allComp.pb(i);
        dfs(i,i);
    }
    
    F0R(i,n) if (comp[i] != 0) 
        for (auto a: adj[i]) if (need[a.s] == 0 && comp[a.f] == 0) {
            //cout << "HUH " << i << " " << a.f << " " << a.s << "\n";
            tmp[comp[i]].pb(a.s);
        }
    
    for (int i: allComp) if (i) test(i);
    for (int i: res) tre[0].pb(i);
}

vector<int> find_roads(int N, vi U, vi V) {
    n = N, u = U, v = V;
    
   // for (int i: v) cout << i << " ";
    //cout << ""
    F0R(i,sz(u)) {
        adj[u[i]].pb({v[i],i});
        adj[v[i]].pb({u[i],i});
        //cout << "OH " << u[i] << " " << v[i] << " " << i << "\n";
    }
    
    FOR(i,1,n) comp[i] = -1;
    while (1) {
        for (int i: tre[0]) comp[u[i]] = comp[v[i]] = 0;
        
        int lef = 0;
        F0R(i,n) if (comp[i] != 0) {
            comp[i] = -1;
            lef ++;
        }
        
        if (lef == 0) break;
        test();
    }
    
    vi ans;
    F0R(i,sz(u)) if (need[i] == 1) ans.pb(i);
    // cout << co << "\n";
    return ans;
}

Compilation message

simurgh.cpp: In function 'void test(int)':
simurgh.cpp:95:17: error: 'count_common_roads' was not declared in this scope
         bes.pb({count_common_roads(z),x});
                 ^~~~~~~~~~~~~~~~~~
simurgh.cpp:95:41: error: no matching function for call to 'std::vector<std::pair<int, int> >::push_back(<brace-enclosed initializer list>)'
         bes.pb({count_common_roads(z),x});
                                         ^
In file included from /usr/include/c++/7/vector:64:0,
                 from /usr/include/c++/7/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
                 from simurgh.cpp:1:
/usr/include/c++/7/bits/stl_vector.h:939:7: note: candidate: void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]
       push_back(const value_type& __x)
       ^~~~~~~~~
/usr/include/c++/7/bits/stl_vector.h:939:7: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type& {aka const std::pair<int, int>&}'
/usr/include/c++/7/bits/stl_vector.h:953:7: note: candidate: void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]
       push_back(value_type&& __x)
       ^~~~~~~~~
/usr/include/c++/7/bits/stl_vector.h:953:7: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::pair<int, int> >::value_type&& {aka std::pair<int, int>&&}'