답안 #321783

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
321783 2020-11-13T11:15:02 Z prasanth30 관광 (NOI14_sightseeing) C++14
0 / 25
3500 ms 172156 KB
#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(u!=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.resize(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

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:118:8: warning: unused variable 'ansss' [-Wunused-variable]
  118 |     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); }
      |                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 1004 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 510 ms 13684 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3533 ms 172156 KB Time limit exceeded
2 Halted 0 ms 0 KB -