oj.uz

Submission #970941

# Submission time Handle Problem Language Result Execution time Memory
970941 2024-04-27T14:38:16 Z maxFedorchuk Graph (BOI20_graph) C++17
100 / 100
 218 ms 37712 KB 
#include <bits/stdc++.h>
using namespace std;

const long long MX=2e5+10,INF=1e18;

vector < pair < long long , long long > > mas[MX];
pair < long long , long double > cnt[MX];
long double ans[MX],vis[MX];

vector < long long > vr;

void DFS(long long zar)
{
    vis[zar]=1;
    vr.push_back(zar);

    for(auto [u,zn]:mas[zar])
    {
        if(!vis[u])
        {
            cnt[u]=make_pair(-cnt[zar].first,zn-cnt[zar].second);
            DFS(u);
        }
    }
}

void cntans()
{
    long double x=-INF,nwx;
    for(auto u:vr)
    {
        for(auto [a,b]:mas[u])
        {
            if(cnt[u].first==0 || cnt[u].first!=cnt[a].first)
            {
                if(cnt[u].second+cnt[a].second!=b)
                {
                    cout<<"NO\n";
                    exit(0);
                }
            }
            else
            {
                nwx=(b-cnt[u].second-cnt[a].second)/(2*cnt[u].first);

                if(x==-INF)
                {
                    x=nwx;
                }

                if(x!=nwx)
                {
                    cout<<"NO\n";
                    exit(0);
                }
            }
        }
    }

    if(x==-INF)
    {
        vector < long double > o;
        for(auto u:vr)
        {
            o.push_back(cnt[u].first*cnt[u].second*-1);
        }
        sort(o.begin(),o.end());

        x=o[o.size()/2];
    }

    for(auto u:vr)
    {
        ans[u]=cnt[u].first*x+cnt[u].second;
    }
}

void vip1(long long a,long long k)
{
    vr.clear();

    cnt[a]=make_pair(0,((k==1)?(0.5):1));
    DFS(a);

    cntans();
}

void vip2(long long a)
{
    vr.clear();

    cnt[a]=make_pair(1,0);
    DFS(a);

    cntans();
}

int main()
{
    //cin.tie(0);
    //ios_base::sync_with_stdio(0);

    long long n,m;
    cin>>n>>m;

    fill(ans+1,ans+1+n,-INF);

    vector < pair < long long ,long long > > vc;
    for(long long i=1;i<=m;i++)
    {
        long long a,b,c;
        cin>>a>>b>>c;
        mas[a].push_back({b,c});
        mas[b].push_back({a,c});

        if(a==b)
        {
            vc.push_back({a,c});
        }
    }

    for(auto u:vc)
    {
        if(ans[u.first]==-INF)
        {
            vip1(u.first,u.second);
        }
    }

    for(long long i=1;i<=n;i++)
    {
        if(ans[i]==-INF)
        {
            vip2(i);
        }
    }

    cout<<"YES\n";
    for(long long i=1;i<=n;i++)
    {
        cout<<fixed<<setprecision(18)<<ans[i]<<" ";
    }
    cout<<"\n";

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
17.0 / 17.0

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

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB answer = YES
2 Correct 2 ms 9052 KB answer = YES
3 Correct 2 ms 9048 KB answer = YES
4 Correct 2 ms 9052 KB answer = NO
5 Correct 2 ms 9052 KB answer = YES
6 Correct 2 ms 9052 KB answer = YES
7 Correct 2 ms 9052 KB answer = YES
8 Correct 2 ms 9052 KB answer = YES
9 Correct 2 ms 9052 KB answer = NO
10 Correct 2 ms 9060 KB answer = YES
11 Correct 2 ms 9052 KB answer = YES
12 Correct 3 ms 9048 KB answer = NO
13 Correct 2 ms 9052 KB answer = YES
14 Correct 2 ms 9052 KB answer = YES
15 Correct 2 ms 9052 KB answer = YES
16 Correct 2 ms 9052 KB answer = YES
17 Correct 2 ms 9052 KB answer = YES
18 Correct 2 ms 9052 KB answer = YES
19 Correct 2 ms 9140 KB answer = YES
20 Correct 2 ms 9052 KB answer = YES
21 Correct 2 ms 9052 KB answer = YES
22 Correct 2 ms 9052 KB answer = NO
23 Correct 2 ms 9276 KB answer = NO
24 Correct 2 ms 9052 KB answer = YES
25 Correct 2 ms 9052 KB answer = YES
26 Correct 2 ms 9204 KB answer = YES
27 Correct 2 ms 9052 KB answer = YES
28 Correct 2 ms 9272 KB answer = YES
29 Correct 2 ms 9052 KB answer = YES
30 Correct 2 ms 9048 KB answer = NO
31 Correct 2 ms 9264 KB answer = YES
32 Correct 2 ms 9052 KB answer = YES
33 Correct 2 ms 9052 KB answer = YES
34 Correct 2 ms 9052 KB answer = YES
35 Correct 2 ms 9104 KB answer = YES
36 Correct 2 ms 9052 KB answer = YES
37 Correct 2 ms 9308 KB answer = YES
38 Correct 2 ms 9308 KB answer = YES
39 Correct 3 ms 9308 KB answer = YES
40 Correct 3 ms 9308 KB answer = YES
41 Correct 2 ms 9308 KB answer = NO
42 Correct 3 ms 9304 KB answer = YES
43 Correct 4 ms 9340 KB answer = YES
44 Correct 3 ms 9308 KB answer = YES
45 Correct 3 ms 9308 KB answer = YES
46 Correct 3 ms 9308 KB answer = YES
47 Correct 3 ms 9308 KB answer = YES
48 Correct 3 ms 9308 KB answer = YES
49 Correct 14 ms 12380 KB answer = YES
50 Correct 17 ms 12632 KB answer = YES
51 Correct 15 ms 12892 KB answer = YES
52 Correct 8 ms 12376 KB answer = NO
53 Correct 3 ms 9308 KB answer = YES
54 Correct 5 ms 11680 KB answer = YES
55 Correct 8 ms 11868 KB answer = YES
56 Correct 14 ms 12456 KB answer = YES
57 Correct 13 ms 12360 KB answer = YES
58 Correct 13 ms 12300 KB answer = YES
59 Correct 12 ms 12300 KB answer = YES
60 Correct 16 ms 12376 KB answer = YES
61 Correct 8 ms 11864 KB answer = YES
62 Correct 102 ms 23484 KB answer = NO
63 Correct 107 ms 23700 KB answer = YES
64 Correct 113 ms 23456 KB answer = NO
65 Correct 109 ms 23628 KB answer = YES
66 Correct 4 ms 9308 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB answer = YES
2 Correct 2 ms 9052 KB answer = YES
3 Correct 2 ms 9048 KB answer = YES
4 Correct 2 ms 9052 KB answer = NO
5 Correct 2 ms 9052 KB answer = YES
6 Correct 2 ms 9052 KB answer = YES
7 Correct 2 ms 9052 KB answer = YES
8 Correct 2 ms 9052 KB answer = YES
9 Correct 2 ms 9052 KB answer = NO
10 Correct 2 ms 9060 KB answer = YES
11 Correct 2 ms 9052 KB answer = YES
12 Correct 3 ms 9048 KB answer = NO
13 Correct 2 ms 9052 KB answer = YES
14 Correct 2 ms 9052 KB answer = YES
15 Correct 2 ms 9052 KB answer = YES
16 Correct 2 ms 9052 KB answer = YES
17 Correct 2 ms 9052 KB answer = YES
18 Correct 2 ms 9052 KB answer = YES
19 Correct 2 ms 9140 KB answer = YES
20 Correct 2 ms 9052 KB answer = YES
21 Correct 2 ms 9052 KB answer = YES
22 Correct 2 ms 9052 KB answer = NO
23 Correct 2 ms 9276 KB answer = NO
24 Correct 2 ms 9052 KB answer = YES
25 Correct 2 ms 9052 KB answer = YES
26 Correct 2 ms 9204 KB answer = YES
27 Correct 2 ms 9052 KB answer = YES
28 Correct 2 ms 9272 KB answer = YES
29 Correct 2 ms 9052 KB answer = YES
30 Correct 2 ms 9048 KB answer = NO
31 Correct 2 ms 9264 KB answer = YES
32 Correct 2 ms 9052 KB answer = YES
33 Correct 2 ms 9052 KB answer = YES
34 Correct 2 ms 9052 KB answer = YES
35 Correct 2 ms 9104 KB answer = YES
36 Correct 2 ms 9052 KB answer = YES
37 Correct 2 ms 9308 KB answer = YES
38 Correct 2 ms 9308 KB answer = YES
39 Correct 3 ms 9308 KB answer = YES
40 Correct 3 ms 9308 KB answer = YES
41 Correct 2 ms 9308 KB answer = NO
42 Correct 3 ms 9304 KB answer = YES
43 Correct 4 ms 9340 KB answer = YES
44 Correct 3 ms 9308 KB answer = YES
45 Correct 3 ms 9308 KB answer = YES
46 Correct 3 ms 9308 KB answer = YES
47 Correct 3 ms 9308 KB answer = YES
48 Correct 3 ms 9308 KB answer = YES
49 Correct 14 ms 12380 KB answer = YES
50 Correct 17 ms 12632 KB answer = YES
51 Correct 15 ms 12892 KB answer = YES
52 Correct 8 ms 12376 KB answer = NO
53 Correct 3 ms 9308 KB answer = YES
54 Correct 5 ms 11680 KB answer = YES
55 Correct 8 ms 11868 KB answer = YES
56 Correct 14 ms 12456 KB answer = YES
57 Correct 13 ms 12360 KB answer = YES
58 Correct 13 ms 12300 KB answer = YES
59 Correct 12 ms 12300 KB answer = YES
60 Correct 16 ms 12376 KB answer = YES
61 Correct 8 ms 11864 KB answer = YES
62 Correct 102 ms 23484 KB answer = NO
63 Correct 107 ms 23700 KB answer = YES
64 Correct 113 ms 23456 KB answer = NO
65 Correct 109 ms 23628 KB answer = YES
66 Correct 4 ms 9308 KB answer = YES
67 Correct 129 ms 30224 KB answer = YES
68 Correct 120 ms 30168 KB answer = YES
69 Correct 115 ms 30052 KB answer = YES
70 Correct 183 ms 37712 KB answer = YES
71 Correct 115 ms 30152 KB answer = YES
72 Correct 131 ms 24220 KB answer = YES
73 Correct 126 ms 24392 KB answer = YES
74 Correct 95 ms 21452 KB answer = YES
75 Correct 45 ms 19912 KB answer = NO
76 Correct 16 ms 12636 KB answer = YES
77 Correct 32 ms 14000 KB answer = YES
78 Correct 53 ms 16204 KB answer = YES
79 Correct 123 ms 22856 KB answer = YES
80 Correct 88 ms 21572 KB answer = YES
81 Correct 73 ms 24900 KB answer = NO
82 Correct 136 ms 29716 KB answer = YES
83 Correct 142 ms 30920 KB answer = YES
84 Correct 146 ms 30752 KB answer = YES
85 Correct 127 ms 30300 KB answer = YES
86 Correct 125 ms 30176 KB answer = YES
87 Correct 72 ms 23504 KB answer = NO
88 Correct 137 ms 26824 KB answer = YES
89 Correct 138 ms 23052 KB answer = YES
90 Correct 117 ms 22864 KB answer = YES
91 Correct 120 ms 23380 KB answer = YES
92 Correct 63 ms 18252 KB answer = YES
93 Correct 62 ms 18256 KB answer = YES
94 Correct 83 ms 28648 KB answer = NO
95 Correct 67 ms 21584 KB answer = NO
96 Correct 218 ms 35204 KB answer = YES
97 Correct 77 ms 28108 KB answer = NO