oj.uz

Submission #328468

# Submission time Handle Problem Language Result Execution time Memory
328468 2020-11-16T17:16:25 Z ishi_10 Sightseeing (NOI14_sightseeing) C++14
15 / 25
 3500 ms 123732 KB 
#include<iostream>
#include<cmath>
#include<bits/stdc++.h>
#include<string.h>
#include <algorithm>
using namespace std;
typedef long long int ll;
const ll maxn=(5*1e6)+1;
const ll mod=100000000;
const int N = 5e5 +5;
typedef  pair<int, int> iPair;
vector<pair<int,int>>f[N];
int visited[N]={0};
int ans[N];
void dfs(int u)
{
    visited[u]=1;
    for (const auto &ab : f[u])
    {
        int v=ab.first;
        int w=ab.second;
        if(visited[v]==1) continue;
        ans[v] = min(ans[u], w);
        dfs(v);
    }

}
struct Graph
{
    int V, E;
    vector< pair<int, iPair> > edges;
    Graph(int V, int E)
    {
        this->V = V;
        this->E = E;
    }
    void addEdge(int u, int v, int w)
    {
        edges.push_back({w, {u, v}});
    }
    void kruskalMST();
};
struct DisjointSets
{
    int *parent, *rnk;
    int n;
    DisjointSets(int n)
    {
        this->n = n;
        parent = new int[n+1];
        rnk = new int[n+1];
        for (int i = 0; i <= n; i++)
        {
            rnk[i] = 0;
            parent[i] = i;
        }
    }
    int find(int u)
    {
        if (u != parent[u])
            parent[u] = find(parent[u]);
        return parent[u];
    }
    void merge(int x, int y)
    {
        x = find(x), y = find(y);
        if (rnk[x] > rnk[y])
            parent[y] = x;
        else
            parent[x] = y;

        if (rnk[x] == rnk[y])
            rnk[y]++;
    }
};
void Graph::kruskalMST()
{
    //int mst_wt = 0;
    sort(edges.begin(), edges.end());
    reverse(edges.begin(),edges.end());
    DisjointSets ds(V);
    vector< pair<int, iPair> >::iterator it;
    for (it=edges.begin(); it!=edges.end(); it++)
    {
        int u = it->second.first;
        int v = it->second.second;

        int set_u = ds.find(u);
        int set_v = ds.find(v);
        if (set_u != set_v)
        {
            f[u].push_back({v,it->first});
            f[v].push_back({u,it->first});
            //mst_wt += it->first;
            ds.merge(set_u, set_v);
        }
    }

    //return mst_wt;
}
int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    Graph g(n,m);
    int i,a,b,c;
    for(i=0;i<m;i++)
    {
        cin>>a>>b>>c;
        a--;
        b--;
        g.addEdge(a,b,c);
    }
    g.kruskalMST();
    ans[0]=1e12;
    dfs(0);
    /*for(i=0;i<n;i++)
        cout<<ans[i]<<" ";
    */
    while(q--)
    {
        int que;
        cin>>que;
        que--;
        cout<<ans[que]<<"\n";
    }

    cerr<<"\nTime elapsed:"<< 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}
/*
4 4 2
1 2 10
1 3 30
2 4 20
3 4 5
*/

Compilation message

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:115:12: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+12' to '2147483647' [-Woverflow]
  115 |     ans[0]=1e12;
      |            ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12140 KB Output is correct
2 Correct 8 ms 12140 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12268 KB Output is correct
2 Correct 9 ms 12160 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 15460 KB Output is correct
2 Correct 71 ms 15092 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3575 ms 123732 KB Time limit exceeded
2 Halted 0 ms 0 KB -