oj.uz

답안 #93205

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
93205 2019-01-07T08:47:38 Z SamAnd Evacuation plan (IZhO18_plan) C++17
100 / 100
 939 ms 50928 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 100005;
const int INF = 1000000007;
struct ban
{
    int x, d;
    ban(){}
    ban(int x, int d)
    {
        this->x = x;
        this->d = d;
    }
};
bool operator<(const ban& a, const ban& b)
{
    return a.d > b.d;
}

int n, m;
vector<ban> a[N];
int k;
int b[N];

int d[N];
bool c[N];
void djk()
{
    priority_queue<ban> q;
    for (int i = 0; i < k; ++i)
    {
        q.push(ban(b[i], 0));
    }
    while (1)
    {
        ban t;
        do
        {
            if (q.empty())
                return;
            t = q.top();
            q.pop();
        } while (c[t.x]);
        c[t.x] = true;
        d[t.x] = t.d;
        for (int i = 0; i < a[t.x].size(); ++i)
        {
            ban h = a[t.x][i];
            h.d += t.d;
            if (!c[h.x])
                q.push(h);
        }
    }
}

int p[N];
int fi(int x)
{
    if (p[x] == x)
        return x;
    return p[x] = fi(p[x]);
}

void kpc(int x, int y)
{
    x = fi(x);
    y = fi(y);
    p[x] = y;
}

vector<ban> g[N];
void kru()
{
    vector<pair<int, pair<int, int> > > v;
    for (int x = 1; x <= n; ++x)
    {
        for (int i = 0; i < a[x].size(); ++i)
        {
            int y = a[x][i].x;
            v.push_back(m_p(min(d[x], d[y]), m_p(x, y)));
        }
    }
    sort(v.begin(), v.end());
    for (int i = 1; i <= n; ++i)
        p[i] = i;
    for (int i = v.size() - 1; i >= 0; --i)
    {
        int x = v[i].second.first;
        int y = v[i].second.second;
        int z = v[i].first;
        if (fi(x) == fi(y))
            continue;
        kpc(x, y);
        g[x].push_back(ban(y, z));
        g[y].push_back(ban(x, z));
    }
}

int l = 20;
int pp[N][30], minu[N][30];
int tim;
int tin[N], tout[N];
void dfs(int x, int cp, int ck)
{
    tin[x] = tim++;
    pp[x][0] = cp;
    minu[x][0] = ck;
    for (int i = 1; i <= l; ++i)
    {
        pp[x][i] = pp[pp[x][i - 1]][i - 1];
        minu[x][i] = min(minu[x][i - 1], minu[pp[x][i - 1]][i - 1]);
    }
    for (int i = 0; i < g[x].size(); ++i)
    {
        ban h = g[x][i];
        if (h.x == cp)
            continue;
        dfs(h.x, x, h.d);
    }
    tout[x] = tim++;
}

bool par(int x, int y)
{
    return (tin[x] <= tin[y] && tout[x] >= tout[y]);
}

int go(int x, int y)
{
    if (par(x, y))
        return INF;
    int res = INF;
    for (int i = l; i >= 0; --i)
    {
        if (!par(pp[x][i], y))
        {
            res = min(res, minu[x][i]);
            x = pp[x][i];
        }
    }
    res = min(res, minu[x][0]);
    return res;
}

int qry(int x, int y)
{
    return min(go(x, y), go(y, x));
}

int main()
{
    //freopen("input2.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        a[x].push_back(ban(y, z));
        a[y].push_back(ban(x, z));
    }
    scanf("%d", &k);
    for (int i = 0; i < k; ++i)
        scanf("%d", &b[i]);
    djk();
    kru();
    dfs(1, 1, INF);
    int q;
    scanf("%d", &q);
    while (q--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%d\n", qry(x, y));
    }
    return 0;
}

Compilation message

plan.cpp: In function 'void djk()':
plan.cpp:47:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < a[t.x].size(); ++i)
                         ~~^~~~~~~~~~~~~~~
plan.cpp: In function 'void kru()':
plan.cpp:78:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < a[x].size(); ++i)
                         ~~^~~~~~~~~~~~~
plan.cpp: In function 'void dfs(int, int, int)':
plan.cpp:114:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:154:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
plan.cpp:158:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &x, &y, &z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:162:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
plan.cpp:164:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b[i]);
         ~~~~~^~~~~~~~~~~~~
plan.cpp:169:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
plan.cpp:173:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 7 ms 5368 KB Output is correct
3 Correct 7 ms 5368 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 7 ms 5368 KB Output is correct
6 Correct 7 ms 5368 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 8 ms 5368 KB Output is correct
10 Correct 8 ms 5368 KB Output is correct
11 Correct 8 ms 5368 KB Output is correct
12 Correct 7 ms 5372 KB Output is correct
13 Correct 8 ms 5368 KB Output is correct
14 Correct 8 ms 5368 KB Output is correct
15 Correct 7 ms 5368 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 7 ms 5368 KB Output is correct
3 Correct 7 ms 5368 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 7 ms 5368 KB Output is correct
6 Correct 7 ms 5368 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 8 ms 5368 KB Output is correct
10 Correct 8 ms 5368 KB Output is correct
11 Correct 8 ms 5368 KB Output is correct
12 Correct 7 ms 5372 KB Output is correct
13 Correct 8 ms 5368 KB Output is correct
14 Correct 8 ms 5368 KB Output is correct
15 Correct 7 ms 5368 KB Output is correct
16 Correct 255 ms 31300 KB Output is correct
17 Correct 918 ms 50836 KB Output is correct
18 Correct 63 ms 9776 KB Output is correct
19 Correct 214 ms 39080 KB Output is correct
20 Correct 935 ms 50780 KB Output is correct
21 Correct 441 ms 40216 KB Output is correct
22 Correct 293 ms 42116 KB Output is correct
23 Correct 921 ms 50816 KB Output is correct
24 Correct 939 ms 50828 KB Output is correct
25 Correct 928 ms 50684 KB Output is correct
26 Correct 208 ms 39156 KB Output is correct
27 Correct 206 ms 39080 KB Output is correct
28 Correct 214 ms 38416 KB Output is correct
29 Correct 212 ms 39136 KB Output is correct
30 Correct 210 ms 38932 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 5140 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 5076 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 5112 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 378 ms 39616 KB Output is correct
2 Correct 820 ms 50364 KB Output is correct
3 Correct 817 ms 50452 KB Output is correct
4 Correct 204 ms 39468 KB Output is correct
5 Correct 812 ms 50544 KB Output is correct
6 Correct 824 ms 50616 KB Output is correct
7 Correct 813 ms 50420 KB Output is correct
8 Correct 788 ms 50324 KB Output is correct
9 Correct 807 ms 50304 KB Output is correct
10 Correct 870 ms 50428 KB Output is correct
11 Correct 800 ms 50476 KB Output is correct
12 Correct 824 ms 50456 KB Output is correct
13 Correct 816 ms 50392 KB Output is correct
14 Correct 827 ms 50368 KB Output is correct
15 Correct 819 ms 50520 KB Output is correct
16 Correct 813 ms 50340 KB Output is correct
17 Correct 819 ms 50396 KB Output is correct
18 Correct 834 ms 50464 KB Output is correct
19 Correct 211 ms 40800 KB Output is correct
20 Correct 813 ms 50412 KB Output is correct
21 Correct 768 ms 50604 KB Output is correct
22 Correct 148 ms 38808 KB Output is correct
23 Correct 195 ms 37928 KB Output is correct
24 Correct 148 ms 38824 KB Output is correct
25 Correct 144 ms 38300 KB Output is correct
26 Correct 205 ms 38124 KB Output is correct
27 Correct 222 ms 40864 KB Output is correct
28 Correct 151 ms 38916 KB Output is correct
29 Correct 212 ms 40088 KB Output is correct
30 Correct 146 ms 39588 KB Output is correct
31 Correct 209 ms 40004 KB Output is correct

Subtask #5
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 7 ms 5368 KB Output is correct
3 Correct 7 ms 5368 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 7 ms 5368 KB Output is correct
6 Correct 7 ms 5368 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 8 ms 5368 KB Output is correct
10 Correct 8 ms 5368 KB Output is correct
11 Correct 8 ms 5368 KB Output is correct
12 Correct 7 ms 5372 KB Output is correct
13 Correct 8 ms 5368 KB Output is correct
14 Correct 8 ms 5368 KB Output is correct
15 Correct 7 ms 5368 KB Output is correct
16 Correct 255 ms 31300 KB Output is correct
17 Correct 918 ms 50836 KB Output is correct
18 Correct 63 ms 9776 KB Output is correct
19 Correct 214 ms 39080 KB Output is correct
20 Correct 935 ms 50780 KB Output is correct
21 Correct 441 ms 40216 KB Output is correct
22 Correct 293 ms 42116 KB Output is correct
23 Correct 921 ms 50816 KB Output is correct
24 Correct 939 ms 50828 KB Output is correct
25 Correct 928 ms 50684 KB Output is correct
26 Correct 208 ms 39156 KB Output is correct
27 Correct 206 ms 39080 KB Output is correct
28 Correct 214 ms 38416 KB Output is correct
29 Correct 212 ms 39136 KB Output is correct
30 Correct 210 ms 38932 KB Output is correct
31 Correct 6 ms 4984 KB Output is correct
32 Correct 6 ms 5112 KB Output is correct
33 Correct 6 ms 5112 KB Output is correct
34 Correct 6 ms 4984 KB Output is correct
35 Correct 6 ms 4984 KB Output is correct
36 Correct 6 ms 5140 KB Output is correct
37 Correct 6 ms 4984 KB Output is correct
38 Correct 6 ms 5076 KB Output is correct
39 Correct 6 ms 5112 KB Output is correct
40 Correct 6 ms 5112 KB Output is correct
41 Correct 378 ms 39616 KB Output is correct
42 Correct 820 ms 50364 KB Output is correct
43 Correct 817 ms 50452 KB Output is correct
44 Correct 204 ms 39468 KB Output is correct
45 Correct 812 ms 50544 KB Output is correct
46 Correct 824 ms 50616 KB Output is correct
47 Correct 813 ms 50420 KB Output is correct
48 Correct 788 ms 50324 KB Output is correct
49 Correct 807 ms 50304 KB Output is correct
50 Correct 870 ms 50428 KB Output is correct
51 Correct 800 ms 50476 KB Output is correct
52 Correct 824 ms 50456 KB Output is correct
53 Correct 816 ms 50392 KB Output is correct
54 Correct 827 ms 50368 KB Output is correct
55 Correct 819 ms 50520 KB Output is correct
56 Correct 813 ms 50340 KB Output is correct
57 Correct 819 ms 50396 KB Output is correct
58 Correct 834 ms 50464 KB Output is correct
59 Correct 211 ms 40800 KB Output is correct
60 Correct 813 ms 50412 KB Output is correct
61 Correct 768 ms 50604 KB Output is correct
62 Correct 148 ms 38808 KB Output is correct
63 Correct 195 ms 37928 KB Output is correct
64 Correct 148 ms 38824 KB Output is correct
65 Correct 144 ms 38300 KB Output is correct
66 Correct 205 ms 38124 KB Output is correct
67 Correct 222 ms 40864 KB Output is correct
68 Correct 151 ms 38916 KB Output is correct
69 Correct 212 ms 40088 KB Output is correct
70 Correct 146 ms 39588 KB Output is correct
71 Correct 209 ms 40004 KB Output is correct
72 Correct 459 ms 40248 KB Output is correct
73 Correct 917 ms 50840 KB Output is correct
74 Correct 921 ms 50840 KB Output is correct
75 Correct 906 ms 50860 KB Output is correct
76 Correct 900 ms 50832 KB Output is correct
77 Correct 898 ms 50812 KB Output is correct
78 Correct 901 ms 50732 KB Output is correct
79 Correct 913 ms 50788 KB Output is correct
80 Correct 899 ms 50776 KB Output is correct
81 Correct 898 ms 50804 KB Output is correct
82 Correct 899 ms 50928 KB Output is correct
83 Correct 927 ms 50720 KB Output is correct
84 Correct 915 ms 50816 KB Output is correct
85 Correct 924 ms 50772 KB Output is correct
86 Correct 903 ms 50716 KB Output is correct
87 Correct 935 ms 50816 KB Output is correct
88 Correct 903 ms 50772 KB Output is correct
89 Correct 356 ms 41104 KB Output is correct
90 Correct 910 ms 50684 KB Output is correct
91 Correct 875 ms 50892 KB Output is correct
92 Correct 236 ms 38568 KB Output is correct
93 Correct 327 ms 38772 KB Output is correct
94 Correct 231 ms 39460 KB Output is correct
95 Correct 220 ms 38912 KB Output is correct
96 Correct 326 ms 38484 KB Output is correct
97 Correct 366 ms 40028 KB Output is correct
98 Correct 240 ms 39452 KB Output is correct
99 Correct 363 ms 41308 KB Output is correct
100 Correct 229 ms 39344 KB Output is correct