Submission #321811

#	Time	Username	Problem	Language	Result	Execution time	Memory
321811		arujbansal	Sightseeing (NOI14_sightseeing)	C++17	0 / 25	3573 ms	167988 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
     
    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;
    }
    //#define int ll
    vector<int> ans;
    void dfs(int u,int p,int w){
    	if(p!=1)
    	ans[u]=min(w,ans[p]);
    	
    	cerr<<ans[u]<<"\n";
    	for(auto i:adj[u]){
    		if(i.second!=p){
    			dfs(i.second,u,i.first);
    		}
    	}
    }
    signed main(){
        setIO("");
        int n,m,q;cin>>n>>m>>q;
        adj.resize(n+2);
        ans.assign(n+2,0);
         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;
        dfs(1,-1,0);
        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: In function 'int main()':
sightseeing.cpp:118:12: warning: unused variable 'ansss' [-Wunused-variable]
  118 |         ll ansss = kruskal(n, edge);
      |            ^~~~~
sightseeing.cpp: In function 'void io::setIn(std::string)':
sightseeing.cpp:34:39: 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:40: 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