oj.uz

Submission #81598

# Submission time Handle Problem Language Result Execution time Memory
81598 2018-10-25T14:21:53 Z ToadDaveski Evacuation plan (IZhO18_plan) C++14
19 / 100
 1270 ms 64740 KB 
#include <bits/stdc++.h>
#define ll long long
#define fr first
#define sc second
using namespace std;
vector <pair <ll,ll> > v[100001];
ll dp[100001],us[100001],pr[100001];
unordered_set <ll> an[100001];
ll ans[100001];
priority_queue <pair <ll,ll> > q;
vector <pair <ll,pair <ll,ll> > > edges;
ll dfs(ll x,ll y)
{
    us[x]=-1;
    if (x==y) return us[x]=dp[y];
    ll ans=0;
    for(auto to : v[x])
    {
        if (us[to.fr]==0)
            dfs(to.fr,y);
        if (us[to.fr]>0)
            ans=max(ans,us[to.fr]);
    }
    return us[x]=min(ans,dp[x]);
}
bool cmp (pair <ll,ll> a, pair <ll,ll> b)
{
    if (a.sc>=b.sc)
        return 1;
    return 0;
}
ll f(ll x)
{
    if (pr[x]==x) return x;
    else return pr[x]=f(pr[x]);
}
int main()
{
    //ios_base::sync_with_stdio(0);
    ll n,m,Q,k,i,j;
    cin>>n>>m;
    //cout<<3<<endl;
    for(i=1;i<=n;i++)
        dp[i]=1e9;
    for(i=1;i<=m;i++)
    {
        ll x,y,z;
        cin>>x>>y>>z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    cin>>k;
    for(i=1;i<=k;i++)
    {
        ll x,y;
        cin>>x;
        q.push({0,x});
        dp[x]=0;
    }
    //cout<<3<<endl;
    while(!q.empty())
    {
        ll from=q.top().sc;
        ll weight=-q.top().fr;
        q.pop();
        if (dp[from]<weight)
            continue;
        for(auto to : v[from])
        {
            if (dp[to.fr]>dp[from]+to.sc)
            {
                dp[to.fr]=dp[from]+to.sc;
                q.push({-(dp[from]+to.sc),to.fr});
            }
        }
    }
    //cout<<3<<endl;
    cin>>Q;
    for(i=1;i<=Q;i++)
    {
        ll x,y;
        cin>>x>>y;
        an[x].insert(i);
        an[y].insert(i);
    }
    for(i=1;i<=n;i++)
    {
        pr[i]=i;
        for(auto to : v[i])
        {
            edges.push_back({min(dp[to.fr],dp[i]),{i,to.fr}});
        }
    }
    //cout<<edges.size()<<endl;
   sort(edges.begin(),edges.end());
   //cout<<3<<endl;
    for(i=edges.size()-1;i>=0;i--)
    {
        //cout<<i<<endl;
        ll a=f(edges[i].sc.fr);
        ll b=f(edges[i].sc.sc);
        if (a==b) continue;
        if (an[a].size()<an[b].size())
            swap(a,b);
        for(const int& tod : an[b])
        {
            if (an[a].count(tod))
            {
                ans[tod]=edges[i].fr;
                an[a].erase(tod);
                an[b].erase(tod);
            }
            else
            {
                an[a].insert(tod);
            }
        }
        pr[b]=a;
    }
    for(i=1;i<=Q;i++)
        printf("%d\n", ans[i]);
    return 0;
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5

*/

Compilation message

plan.cpp: In function 'int main()':
plan.cpp:55:14: warning: unused variable 'y' [-Wunused-variable]
         ll x,y;
              ^
plan.cpp:121:30: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
         printf("%d\n", ans[i]);
                        ~~~~~~^
plan.cpp:40:18: warning: unused variable 'j' [-Wunused-variable]
     ll n,m,Q,k,i,j;
                  ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 34244 KB Output is correct
2 Correct 1245 ms 62996 KB Output is correct
3 Correct 1257 ms 63048 KB Output is correct
4 Correct 227 ms 20448 KB Output is correct
5 Correct 1248 ms 63028 KB Output is correct
6 Correct 1239 ms 63068 KB Output is correct
7 Correct 1236 ms 63148 KB Output is correct
8 Correct 1252 ms 63328 KB Output is correct
9 Correct 1243 ms 63156 KB Output is correct
10 Correct 1252 ms 63144 KB Output is correct
11 Correct 1254 ms 63096 KB Output is correct
12 Correct 1246 ms 63160 KB Output is correct
13 Correct 1249 ms 63104 KB Output is correct
14 Correct 1232 ms 63048 KB Output is correct
15 Correct 1257 ms 64740 KB Output is correct
16 Correct 1246 ms 63024 KB Output is correct
17 Correct 1250 ms 63064 KB Output is correct
18 Correct 1240 ms 63120 KB Output is correct
19 Correct 234 ms 20460 KB Output is correct
20 Correct 1270 ms 63076 KB Output is correct
21 Correct 1221 ms 62624 KB Output is correct
22 Correct 237 ms 23260 KB Output is correct
23 Correct 245 ms 20860 KB Output is correct
24 Correct 249 ms 23256 KB Output is correct
25 Correct 247 ms 23656 KB Output is correct
26 Correct 250 ms 20936 KB Output is correct
27 Correct 235 ms 20592 KB Output is correct
28 Correct 249 ms 23380 KB Output is correct
29 Correct 234 ms 20492 KB Output is correct
30 Correct 244 ms 23820 KB Output is correct
31 Correct 229 ms 20384 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8184 KB Output isn't correct
2 Halted 0 ms 0 KB -