oj.uz

Submission #286112

# Submission time Handle Problem Language Result Execution time Memory
286112 2020-08-30T06:51:57 Z gratus907 Graph (BOI20_graph) C++17
100 / 100
 324 ms 38252 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define ll long long
#define int ll
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;
const int INF = 1e12;
const int UNDET = 2;
const int PLUS = 1;
const int MINUS = -1;
const int FIXED = 0;
struct edge
{
    int from, to;
    double w;
};
struct node
{
    int ind, var = UNDET;
    double con = 0;
    node(int _ind = 0, int _var = UNDET, double _con = 0.0)
    {ind = _ind; var = _var; con = _con;}
    void print()
    {
        printf("NODE %lld : ",ind);
        if (var == UNDET)
            printf("UNDETERMINED NODE\n");
        else if (var == FIXED)
            printf("%.3lf\n",con);
        else
            printf("%sx + %.3lf\n",(var==PLUS?"+":"-"),con);
    }
};
node ND[101010];
vector <edge> G[101010];
void report_fail()
{
    cout << "NO\n";
    exit(0);
}
bool visited[101010];
vector <int> topo;
map<int, int> topo_order;
void dfs_run(int rt, bool d = 0)
{
    topo.push_back(rt);
    visited[rt] = true;
    if (ND[rt].var == UNDET)
    {
        ND[rt].var = PLUS;
        ND[rt].con = 0.0;
    }
    for (edge E : G[rt])
    {
        int nxt = E.to;
        if (visited[nxt]) continue;
        if (ND[nxt].var == UNDET)
        {
            ND[nxt].con = E.w - ND[rt].con;
            ND[nxt].var = -ND[rt].var;
            dfs_run(nxt, d);
        }
        else
        {
            if (ND[nxt].var == ND[rt].var)
                continue;
            else
            {
                if (ND[nxt].con + ND[rt].con != E.w)
                {
                    if (d)
                    {
                        printf("MISMATCH %lld %lld\n",rt,nxt);
                        ND[rt].print();
                        ND[nxt].print();
                    }
                    report_fail();
                }
                else continue;
            }
        }
    }
    return;
}
double find_x()
{
    double x = INF;
    for (int i = topo.size()-1; i >= 0; i--)
    {
        int cur = topo[i];
        for (edge E : G[cur])
        {
            int nxt = E.to;
            if (topo_order[nxt] < i)
            {
                if (ND[nxt].var == ND[cur].var)
                {
                    double cons = ND[nxt].con + ND[cur].con;
                    double vars = ND[nxt].var + ND[cur].var;
                    return (E.w - cons) / vars;
                }
                else
                {
                    if (ND[nxt].var + ND[cur].var == 0)
                    {
                        if (ND[nxt].con + ND[cur].con != E.w)
                            report_fail();
                    }
                }
            }
            else continue;
        }
    }
    vector <double> convals;
    for (int i = 0; i<topo.size(); i++)
    {
        convals.push_back((-1)*(ND[topo[i]].var)*ND[topo[i]].con);
    }
    sort(all(convals));
    int sz = convals.size();
    return convals[sz/2];
}
void fix_dfs(int rt, double x)
{
    visited[rt] = true;
    ND[rt].con = ND[rt].var * x + ND[rt].con;
    ND[rt].var = FIXED;
    for (edge E : G[rt])
    {
        if (ND[E.to].var != FIXED)
            fix_dfs(E.to, x);
    }
    return;
}
void const_fix(int rt, double xconst)
{
    visited[rt] = true;
    ND[rt].con = xconst;
    ND[rt].var = FIXED;
    for (edge E : G[rt])
    {
        if (ND[E.to].var != FIXED)
            const_fix(E.to, E.w-xconst);
    }
    return;
}
vector <pair<int, double>> cf;
int32_t main()
{
    usecppio
    int n, m;
    cin >> n >> m;
    for (int i = 1; i<=n; i++) ND[i].ind = i;
    for (int i = 0; i<m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        edge e = {u, v, w*1.0};
        edge erev = {v, u, w*1.0};
        G[u].push_back(e);
        G[v].push_back(erev);
        if (u == v)
            cf.push_back({u, w*0.5});
    }
    for (auto [u, w] : cf)
    {
        if (!visited[u])
            const_fix(u, w);
    }
    for (int i = 1; i<=n; i++)
    {
        topo.clear();
        topo_order.clear();
        if (!visited[i])
        {
            dfs_run(i);
            for (int j = 0; j<topo.size(); j++)
            {
                topo_order[topo[j]] = j;
            }
            double xval = find_x();
            fix_dfs(i, xval);
        }
    }
    for (int i = 1; i<=n; i++)
    {
        for (edge E : G[i])
        {
            if (ND[E.from].con + ND[E.to].con != E.w)
                report_fail();
        }
    }
    cout << "YES\n";
    for (int i = 1; i<=n; i++)
        cout << fixed << setprecision(10) << ND[i].con << ' ';
}

Compilation message

Graph.cpp: In function 'double find_x()':
Graph.cpp:118:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for (int i = 0; i<topo.size(); i++)
      |                     ~^~~~~~~~~~~~
Graph.cpp:90:12: warning: unused variable 'x' [-Wunused-variable]
   90 |     double x = INF;
      |            ^
Graph.cpp: In function 'int32_t main()':
Graph.cpp:180:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |             for (int j = 0; j<topo.size(); j++)
      |                             ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB answer = YES
2 Correct 3 ms 5120 KB answer = YES
3 Correct 3 ms 5120 KB answer = YES
4 Correct 3 ms 5120 KB answer = NO
5 Correct 3 ms 5120 KB answer = YES
6 Correct 3 ms 5120 KB answer = YES
7 Correct 3 ms 5120 KB answer = YES
8 Correct 3 ms 5120 KB answer = YES
9 Correct 3 ms 5120 KB answer = NO
10 Correct 3 ms 5120 KB answer = YES
11 Correct 3 ms 5120 KB answer = YES
12 Correct 3 ms 5120 KB answer = NO
13 Correct 3 ms 5120 KB answer = YES
14 Correct 3 ms 5120 KB answer = YES
15 Correct 3 ms 5120 KB answer = YES
16 Correct 3 ms 5120 KB answer = YES
17 Correct 3 ms 5120 KB answer = YES
18 Correct 3 ms 5120 KB answer = YES
19 Correct 3 ms 5120 KB answer = YES
20 Correct 4 ms 5120 KB answer = YES
21 Correct 3 ms 5120 KB answer = YES
22 Correct 3 ms 5120 KB answer = NO
23 Correct 3 ms 5120 KB answer = NO

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB answer = YES
2 Correct 3 ms 5120 KB answer = YES
3 Correct 3 ms 5120 KB answer = YES
4 Correct 3 ms 5120 KB answer = NO
5 Correct 3 ms 5120 KB answer = YES
6 Correct 3 ms 5120 KB answer = YES
7 Correct 3 ms 5120 KB answer = YES
8 Correct 3 ms 5120 KB answer = YES
9 Correct 3 ms 5120 KB answer = NO
10 Correct 3 ms 5120 KB answer = YES
11 Correct 3 ms 5120 KB answer = YES
12 Correct 3 ms 5120 KB answer = NO
13 Correct 3 ms 5120 KB answer = YES
14 Correct 3 ms 5120 KB answer = YES
15 Correct 3 ms 5120 KB answer = YES
16 Correct 3 ms 5120 KB answer = YES
17 Correct 3 ms 5120 KB answer = YES
18 Correct 3 ms 5120 KB answer = YES
19 Correct 3 ms 5120 KB answer = YES
20 Correct 4 ms 5120 KB answer = YES
21 Correct 3 ms 5120 KB answer = YES
22 Correct 3 ms 5120 KB answer = NO
23 Correct 3 ms 5120 KB answer = NO
24 Correct 3 ms 5120 KB answer = YES
25 Correct 3 ms 5120 KB answer = YES
26 Correct 4 ms 5120 KB answer = YES
27 Correct 4 ms 5120 KB answer = YES
28 Correct 3 ms 5120 KB answer = YES
29 Correct 4 ms 5120 KB answer = YES
30 Correct 4 ms 5120 KB answer = NO
31 Correct 3 ms 5120 KB answer = YES
32 Correct 4 ms 5120 KB answer = YES
33 Correct 3 ms 5120 KB answer = YES
34 Correct 4 ms 5120 KB answer = YES
35 Correct 3 ms 5120 KB answer = YES
36 Correct 4 ms 5120 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB answer = YES
2 Correct 3 ms 5120 KB answer = YES
3 Correct 3 ms 5120 KB answer = YES
4 Correct 3 ms 5120 KB answer = NO
5 Correct 3 ms 5120 KB answer = YES
6 Correct 3 ms 5120 KB answer = YES
7 Correct 3 ms 5120 KB answer = YES
8 Correct 3 ms 5120 KB answer = YES
9 Correct 3 ms 5120 KB answer = NO
10 Correct 3 ms 5120 KB answer = YES
11 Correct 3 ms 5120 KB answer = YES
12 Correct 3 ms 5120 KB answer = NO
13 Correct 3 ms 5120 KB answer = YES
14 Correct 3 ms 5120 KB answer = YES
15 Correct 3 ms 5120 KB answer = YES
16 Correct 3 ms 5120 KB answer = YES
17 Correct 3 ms 5120 KB answer = YES
18 Correct 3 ms 5120 KB answer = YES
19 Correct 3 ms 5120 KB answer = YES
20 Correct 4 ms 5120 KB answer = YES
21 Correct 3 ms 5120 KB answer = YES
22 Correct 3 ms 5120 KB answer = NO
23 Correct 3 ms 5120 KB answer = NO
24 Correct 3 ms 5120 KB answer = YES
25 Correct 3 ms 5120 KB answer = YES
26 Correct 4 ms 5120 KB answer = YES
27 Correct 4 ms 5120 KB answer = YES
28 Correct 3 ms 5120 KB answer = YES
29 Correct 4 ms 5120 KB answer = YES
30 Correct 4 ms 5120 KB answer = NO
31 Correct 3 ms 5120 KB answer = YES
32 Correct 4 ms 5120 KB answer = YES
33 Correct 3 ms 5120 KB answer = YES
34 Correct 4 ms 5120 KB answer = YES
35 Correct 3 ms 5120 KB answer = YES
36 Correct 4 ms 5120 KB answer = YES
37 Correct 4 ms 5120 KB answer = YES
38 Correct 4 ms 5120 KB answer = YES
39 Correct 4 ms 5248 KB answer = YES
40 Correct 5 ms 5248 KB answer = YES
41 Correct 4 ms 5376 KB answer = NO
42 Correct 5 ms 5248 KB answer = YES
43 Correct 5 ms 5248 KB answer = YES
44 Correct 5 ms 5248 KB answer = YES
45 Correct 4 ms 5248 KB answer = YES
46 Correct 4 ms 5120 KB answer = YES
47 Correct 4 ms 5248 KB answer = YES
48 Correct 4 ms 5248 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB answer = YES
2 Correct 3 ms 5120 KB answer = YES
3 Correct 3 ms 5120 KB answer = YES
4 Correct 3 ms 5120 KB answer = NO
5 Correct 3 ms 5120 KB answer = YES
6 Correct 3 ms 5120 KB answer = YES
7 Correct 3 ms 5120 KB answer = YES
8 Correct 3 ms 5120 KB answer = YES
9 Correct 3 ms 5120 KB answer = NO
10 Correct 3 ms 5120 KB answer = YES
11 Correct 3 ms 5120 KB answer = YES
12 Correct 3 ms 5120 KB answer = NO
13 Correct 3 ms 5120 KB answer = YES
14 Correct 3 ms 5120 KB answer = YES
15 Correct 3 ms 5120 KB answer = YES
16 Correct 3 ms 5120 KB answer = YES
17 Correct 3 ms 5120 KB answer = YES
18 Correct 3 ms 5120 KB answer = YES
19 Correct 3 ms 5120 KB answer = YES
20 Correct 4 ms 5120 KB answer = YES
21 Correct 3 ms 5120 KB answer = YES
22 Correct 3 ms 5120 KB answer = NO
23 Correct 3 ms 5120 KB answer = NO
24 Correct 3 ms 5120 KB answer = YES
25 Correct 3 ms 5120 KB answer = YES
26 Correct 4 ms 5120 KB answer = YES
27 Correct 4 ms 5120 KB answer = YES
28 Correct 3 ms 5120 KB answer = YES
29 Correct 4 ms 5120 KB answer = YES
30 Correct 4 ms 5120 KB answer = NO
31 Correct 3 ms 5120 KB answer = YES
32 Correct 4 ms 5120 KB answer = YES
33 Correct 3 ms 5120 KB answer = YES
34 Correct 4 ms 5120 KB answer = YES
35 Correct 3 ms 5120 KB answer = YES
36 Correct 4 ms 5120 KB answer = YES
37 Correct 4 ms 5120 KB answer = YES
38 Correct 4 ms 5120 KB answer = YES
39 Correct 4 ms 5248 KB answer = YES
40 Correct 5 ms 5248 KB answer = YES
41 Correct 4 ms 5376 KB answer = NO
42 Correct 5 ms 5248 KB answer = YES
43 Correct 5 ms 5248 KB answer = YES
44 Correct 5 ms 5248 KB answer = YES
45 Correct 4 ms 5248 KB answer = YES
46 Correct 4 ms 5120 KB answer = YES
47 Correct 4 ms 5248 KB answer = YES
48 Correct 4 ms 5248 KB answer = YES
49 Correct 20 ms 6832 KB answer = YES
50 Correct 17 ms 7040 KB answer = YES
51 Correct 20 ms 7216 KB answer = YES
52 Correct 13 ms 6912 KB answer = NO
53 Correct 5 ms 5248 KB answer = YES
54 Correct 7 ms 5504 KB answer = YES
55 Correct 11 ms 6012 KB answer = YES
56 Correct 20 ms 6832 KB answer = YES
57 Correct 17 ms 6272 KB answer = YES
58 Correct 17 ms 6376 KB answer = YES
59 Correct 12 ms 5888 KB answer = YES
60 Correct 19 ms 6528 KB answer = YES
61 Correct 8 ms 5504 KB answer = YES
62 Correct 79 ms 21240 KB answer = NO
63 Correct 93 ms 21368 KB answer = YES
64 Correct 83 ms 21328 KB answer = NO
65 Correct 88 ms 21624 KB answer = YES
66 Correct 6 ms 5376 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB answer = YES
2 Correct 3 ms 5120 KB answer = YES
3 Correct 3 ms 5120 KB answer = YES
4 Correct 3 ms 5120 KB answer = NO
5 Correct 3 ms 5120 KB answer = YES
6 Correct 3 ms 5120 KB answer = YES
7 Correct 3 ms 5120 KB answer = YES
8 Correct 3 ms 5120 KB answer = YES
9 Correct 3 ms 5120 KB answer = NO
10 Correct 3 ms 5120 KB answer = YES
11 Correct 3 ms 5120 KB answer = YES
12 Correct 3 ms 5120 KB answer = NO
13 Correct 3 ms 5120 KB answer = YES
14 Correct 3 ms 5120 KB answer = YES
15 Correct 3 ms 5120 KB answer = YES
16 Correct 3 ms 5120 KB answer = YES
17 Correct 3 ms 5120 KB answer = YES
18 Correct 3 ms 5120 KB answer = YES
19 Correct 3 ms 5120 KB answer = YES
20 Correct 4 ms 5120 KB answer = YES
21 Correct 3 ms 5120 KB answer = YES
22 Correct 3 ms 5120 KB answer = NO
23 Correct 3 ms 5120 KB answer = NO
24 Correct 3 ms 5120 KB answer = YES
25 Correct 3 ms 5120 KB answer = YES
26 Correct 4 ms 5120 KB answer = YES
27 Correct 4 ms 5120 KB answer = YES
28 Correct 3 ms 5120 KB answer = YES
29 Correct 4 ms 5120 KB answer = YES
30 Correct 4 ms 5120 KB answer = NO
31 Correct 3 ms 5120 KB answer = YES
32 Correct 4 ms 5120 KB answer = YES
33 Correct 3 ms 5120 KB answer = YES
34 Correct 4 ms 5120 KB answer = YES
35 Correct 3 ms 5120 KB answer = YES
36 Correct 4 ms 5120 KB answer = YES
37 Correct 4 ms 5120 KB answer = YES
38 Correct 4 ms 5120 KB answer = YES
39 Correct 4 ms 5248 KB answer = YES
40 Correct 5 ms 5248 KB answer = YES
41 Correct 4 ms 5376 KB answer = NO
42 Correct 5 ms 5248 KB answer = YES
43 Correct 5 ms 5248 KB answer = YES
44 Correct 5 ms 5248 KB answer = YES
45 Correct 4 ms 5248 KB answer = YES
46 Correct 4 ms 5120 KB answer = YES
47 Correct 4 ms 5248 KB answer = YES
48 Correct 4 ms 5248 KB answer = YES
49 Correct 20 ms 6832 KB answer = YES
50 Correct 17 ms 7040 KB answer = YES
51 Correct 20 ms 7216 KB answer = YES
52 Correct 13 ms 6912 KB answer = NO
53 Correct 5 ms 5248 KB answer = YES
54 Correct 7 ms 5504 KB answer = YES
55 Correct 11 ms 6012 KB answer = YES
56 Correct 20 ms 6832 KB answer = YES
57 Correct 17 ms 6272 KB answer = YES
58 Correct 17 ms 6376 KB answer = YES
59 Correct 12 ms 5888 KB answer = YES
60 Correct 19 ms 6528 KB answer = YES
61 Correct 8 ms 5504 KB answer = YES
62 Correct 79 ms 21240 KB answer = NO
63 Correct 93 ms 21368 KB answer = YES
64 Correct 83 ms 21328 KB answer = NO
65 Correct 88 ms 21624 KB answer = YES
66 Correct 6 ms 5376 KB answer = YES
67 Correct 163 ms 27728 KB answer = YES
68 Correct 148 ms 27624 KB answer = YES
69 Correct 122 ms 27372 KB answer = YES
70 Correct 172 ms 38252 KB answer = YES
71 Correct 124 ms 27372 KB answer = YES
72 Correct 291 ms 21736 KB answer = YES
73 Correct 234 ms 21480 KB answer = YES
74 Correct 142 ms 19060 KB answer = YES
75 Correct 92 ms 17912 KB answer = NO
76 Correct 24 ms 7200 KB answer = YES
77 Correct 51 ms 9268 KB answer = YES
78 Correct 97 ms 12276 KB answer = YES
79 Correct 239 ms 19436 KB answer = YES
80 Correct 155 ms 19188 KB answer = YES
81 Correct 126 ms 23144 KB answer = NO
82 Correct 197 ms 27116 KB answer = YES
83 Correct 225 ms 27884 KB answer = YES
84 Correct 324 ms 27996 KB answer = YES
85 Correct 160 ms 27624 KB answer = YES
86 Correct 134 ms 27500 KB answer = YES
87 Correct 92 ms 16884 KB answer = NO
88 Correct 227 ms 20488 KB answer = YES
89 Correct 131 ms 14072 KB answer = YES
90 Correct 133 ms 14072 KB answer = YES
91 Correct 141 ms 14456 KB answer = YES
92 Correct 59 ms 9720 KB answer = YES
93 Correct 59 ms 9720 KB answer = YES
94 Correct 137 ms 26472 KB answer = NO
95 Correct 83 ms 13048 KB answer = NO
96 Correct 239 ms 26744 KB answer = YES
97 Correct 69 ms 26088 KB answer = NO