Submission #1040743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040743		vjudge1	Evacuation plan (IZhO18_plan)	C++17	19 / 100	408 ms	51208 KiB

plan

#include <bits/stdc++.h>
#define fi(i, a, b) for( int i = a; i <= b; i++ )
#define fid(i, a, b) for( int i = a; i >= b; i-- )
#define getbit(x, i) ((x>>i)&1)
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define st first
#define nd second
#define mp make_pair
#define HTManh ""
#define maxn 100009
#define endl '\n'
using namespace std;

int n, m, k, truyvan;
vector<pll> a[100009];
pii tv[100009];

ll kq[100009];

ll L[100009];

void dij(int xp)
{
    priority_queue<pll> q;
    fi(i,1,n) L[i] = 1e18;
    L[0] = 0;
    q.push({0, 0});
    while(q.size())
    {
        int u = q.top().nd;
        q.pop();

        for(pll tg: a[u])
        {
            int v = tg.st;
            ll kc = tg.nd;
            if (L[v] > L[u] + kc)
            {
                L[v] = L[u] + kc;
                q.push({-L[v], v});
            }
        }
    }
}

pll idk[100009];
vector<int> cay[400009];
vector<pair<int, pii>> q[2];
bool flag;

bool xd[100009];
int goc[100009];

int get(int u)
{
    if (u == goc[u]) return u;
    return (goc[u] = get(goc[u]));
}

void hop(int u, int v)
{
    u = get(u), v = get(v);
    if (u != v) goc[u] = v;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	if (fopen(HTManh".inp", "r"))
    {
        freopen(HTManh".inp", "r", stdin);
        freopen(HTManh".out", "w", stdout);
    }

    cin >> n >> m;
    fi(i,1,m)
    {
        int x,y,z;
        cin >> x >> y >> z;
        a[x].pb({y,z});
        a[y].pb({x,z});
    }
    cin >> k;
    fi(i,1,k)
    {
        int x;
        cin >> x;
        a[0].pb({x, 0});
    }
    cin >> truyvan;
    fi(i,1,truyvan)
    {
        int x, y;
        cin >> x >> y;
        tv[i] = {x, y};
    }
    dij(0);
//    fi(i,1,n) cout << L[i] << " ";
//    cout << endl;

    fi(i,1,n) idk[i] = {-L[i], i};
    sort(idk+1,idk+n+1);
    //fi(i,1,n) cout << -idk[i].st << " " << idk[i].nd << endl;

    fi(i,1,n) cay[1].pb(i);
    q[0].pb({1, {1,n}});
    while(q[flag].size())
    {
        int pre = 0;
        iota(goc+1,goc+n+1,1);
        fi(u,1,n) xd[u] = 0;
        for(pair<int, pii> tg: q[flag])
        {
            int goc = tg.st;
            int l = tg.nd.st;
            int r = tg.nd.nd;

            if (l == r)
            {
                for(int i: cay[goc])
                {
                    kq[i] = -idk[l].st;
                }
                continue;
            }

            int g = (l+r)/2;
            fi(i,pre+1,g)
            {
                int u = idk[i].nd;
                xd[u] = 1;
                for(pii tg2: a[u])
                {
                    int v = tg2.st;
                    if (!xd[v]) continue;
                    hop(u,v);
                }
            }
            pre = g;

            for(int i: cay[goc])
            {
                if (get(tv[i].st) == get(tv[i].nd)) cay[goc*2].pb(i);
                else cay[goc*2+1].pb(i);
            }

            if (cay[goc*2].size()) q[1-flag].pb({goc*2, {l, g}});
            if (cay[goc*2+1].size()) q[1-flag].pb({goc*2+1, {g+1, r}});
        }
        q[flag].clear();
        flag = 1-flag;
    }

    fi(i,1,truyvan) cout << kq[i] << endl;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen(HTManh".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen(HTManh".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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