Submission #321808

#	Time	Username	Problem	Language	Result	Execution time	Memory
321808		saarang123	Sightseeing (NOI14_sightseeing)	C++14	0 / 25	3586 ms	168204 KiB

sightseeing

#include <bits/stdc++.h>
using namespace std;
//actual solution is at bottom//
////<pbds>////
/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>,
    rb_tree_tag, tree_order_statistics_node_update>;
// change null_type for map
// change less to less_equal for multiset
#define ook order_of_key
#define fbo find_by_order*/
///</pbds>///

#define int long long int
//#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define google(i) cout<<"Case #"<<i<<" :";
///<constants>///
const int MOD = 1e9+7; // 998244353; // = (119<<23)+1
const int MX = 2e5+5;
const int  INF = 1e18;
const ld PI = 4*atan((ld)1);
const int xd[4] = {0,1,0,-1}, yd[4] = {1,0,-1,0};
///</constants>///

///<IO>///
namespace io {
    void setIn(string s) { freopen(s.c_str(),"r",stdin); }
    void setOut(string s) { freopen(s.c_str(),"w",stdout); }
    void setIO(string s = "") {
        ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
        // cin.exceptions(cin.failbit); // ex. throws exception when you try to read letter into int
        if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
    }
}

using namespace io;
///</IO>///

///<execution-time>///
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
/*example for clock usage
    clock_t z = clock();
    debug("Total Time: %.3f\n", (double)(clock() - z) / CLOCKS_PER_SEC);
*/
///</execution-time>///
               //weight final vertex
vector<vector<pair<int,int>>> adj;
int n;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

#define trav(a,x) for (auto& a: x)
#define all(x) begin(x), end(x)
#define mp make_pair
#define f first
#define s second
#define int long long

struct DSU {
    vi e; void init(int N) { e = vi(N,-1); }
    // get representive component, uses path compression
    int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
    bool sameSet(int a, int b) { return get(a) == get(b); }
    int size(int x) { return -e[get(x)]; }
    bool unite(int x, int y) { // union by size
        x = get(x), y = get(y); if (x == y) return 0;
        if (e[x] > e[y]) swap(x,y);
        e[x] += e[y]; e[y] = x; return 1;
    }
};

int comp;
template<class T> T kruskal(int N, vector<pair<T,pi>> ed) {
    sort(all(ed));
    reverse(all(ed));
    T ans = 0; DSU D; D.init(N); // edges that unite are in MST
    trav(a,ed)
    if (D.unite(a.s.f,a.s.s)) {
        adj[a.s.f].pb({a.f,a.s.s});
        adj[a.s.s].pb({a.f,a.s.f});
        cerr<<a.s.f<<" "<<a.s.s<<" >="<<a.f<<"\n";
        comp--;
    }
    return ans;
}

vector<int> ans;

signed main(){
    setIO("");
    int n,m,q;cin>>n>>m>>q;
    adj.resize(n+2);
    ans.resize(n+2, INF);
     vector<pair<ll,pi>> edge;
    for (int i = 0; i < m; i++){
        int a, b; ll c;
        cin >> a >> b >> c;
        edge.push_back(mp(c, mp(a, b)));
    }
    comp = n;
    ll ansss = kruskal(n, edge);
    ans[1]=INF;
    function<void(int v, int p, int mx)> dfs = [&] (int v, int p, int mx) {
        ans[v] = min(ans[v], mx);
        for(auto tx : adj[v]) if(tx.s != p) {
            dfs(tx.s, v, min(tx.f, mx));
        }
    };
    dfs(1, -1, INF);
    while(q--){
    	int x;cin>>x;
    	cout<<ans[x]<<"\n";
    }
    return 0;
}
/* stuff you should look for
    * check whether you have read the problem correctly
    * int overflow, array bounds
    * special cases (n=1?), slow multiset operations
    * do smth instead of nothing and stay organized
*/

Compilation message (stderr)

sightseeing.cpp:65: warning: "int" redefined
   65 | #define int long long
      | 
sightseeing.cpp:17: note: this is the location of the previous definition
   17 | #define int long long int
      | 
sightseeing.cpp: In function 'int main()':
sightseeing.cpp:109:8: warning: unused variable 'ansss' [-Wunused-variable]
  109 |     ll ansss = kruskal(n, edge);
      |        ^~~~~
sightseeing.cpp: In function 'void io::setIn(std::string)':
sightseeing.cpp:34:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   34 |     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp: In function 'void io::setOut(std::string)':
sightseeing.cpp:35:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   35 |     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
      |                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 6
• Subtask 4: 0 / 10