Submission #93665

#	Time	Username	Problem	Language	Result	Execution time	Memory
93665		Mercenary	Evacuation plan (IZhO18_plan)	C++11	100 / 100	821 ms	38812 KiB

plan

#include<bits/stdc++.h>

using namespace std;
#define taskname "TEST"
#define pb	push_back
typedef long double ld;
typedef long long ll;
const int maxn = 1e5 + 5;
typedef pair<int,int> tpair;
#define mp make_pair

int n , m , k , q , a[maxn];
vector<tpair> adj[maxn];
set<int>* s[maxn];
int res[maxn] , d[maxn];

void enter()
{
    cin >> n >> m;
    for(int i = 1 ; i <= m ; ++i)
    {
        int u , v , w;cin >> u >> v >> w;
        adj[u].pb(mp(v,w));
        adj[v].pb(mp(u,w));
    }
    cin >> k;
    for(int i = 1 ; i <= k ; ++i)cin >> a[i];
}
priority_queue<tpair,vector<tpair>,greater<tpair>> pq;
void dij()
{
    fill_n(d,maxn,(int)1e9);
    for(int i = 1 ; i <= k ; ++i)
    {
        d[a[i]] = 0;
        pq.push(mp(0,a[i]));
    }
    while(!pq.empty())
    {
        auto u = pq.top();pq.pop();
        if(d[u.second] != u.first)continue;
        for(auto c : adj[u.second])
        {
            if(d[c.first] > u.first + c.second)
            {
                d[c.first] = u.first + c.second;
                pq.push(mp(d[c.first],c.first));
            }
        }
    }
}

int lab[maxn];

int finds(int u)
{
    return lab[u] < 0 ? u : lab[u] = finds(lab[u]);
}

void Uni(int now , int u , int v)
{
    u = finds(u);
    v = finds(v);
    if(u == v)return;
    if(lab[u] > lab[v])swap(u,v);
    lab[u] += lab[v];
    lab[v] = u;
    if(s[u]->size() < s[v]->size())swap(s[u],s[v]);
    for(auto c : (*s[v])){
        if(s[u]->find(c) != s[u]->end())res[c] = min(res[c],now) , s[u]->erase(c);
        else s[u]->insert(c);
    }
    s[v]->clear();
}

void solve()
{
    cin >> q;
    for(int i = 1 ; i <= n ; ++i)s[i] = new set<int>;
    for(int i = 1 ; i <= q ; ++i)
    {
        int u , v;cin >> u >> v;
        if(d[u] == 0 || d[v] == 0)
        {
            res[i] = 0;
            continue;
        }
//        if(s[u] == NULL)s[u] = new set<int>;
        res[i] = min(d[u],d[v]);
        s[u]->insert(i);
        s[v]->insert(i);
    }
    fill_n(lab,maxn,-1);
    vector<tpair> v;
    for(int i = 1 ; i <= n ; ++i)v.pb(mp(d[i],i));
    sort(v.begin(),v.end(),greater<tpair>());
    for(auto u : v)
    {
        for(auto c : adj[u.second])
            if(d[c.first] >= u.first)Uni(u.first,u.second,c.first);
    }
    for(int i = 1 ; i <= q ; ++i)
        cout << res[i] << '\n';
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	if(fopen(taskname".INP","r"))
        freopen(taskname".INP", "r",stdin) ,
        freopen(taskname".OUT", "w",stdout);
    enter();
    dij();
    solve();
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:111:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".INP", "r",stdin) ,
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
         freopen(taskname".OUT", "w",stdout);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
plan.cpp:111:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46