oj.uz

Submission #720746

# Submission time Handle Problem Language Result Execution time Memory
720746 2023-04-09T08:50:20 Z n0sk1ll Graph (BOI20_graph) C++17
100 / 100
 162 ms 22852 KB 
#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

const double eps=1e-9;

vector<pii> w1,w2;
vector<vector<pii>> g(100005); //(gde, boja)
int znak[100005],shift[100005]; //x - c, ili mozda x+c, takodje proverava posecenost ako znak[]=0
ld ans[100005];

bool determined=false; //da li x vec mora biti postavljeno jednacinama?
double x; //ako je determined, sta je ona?

vector<int> poseceni;
void dfs(int p)
{
    poseceni.pb(p);
    for (auto it : g[p])
    {
        if (znak[it.xx])
        {
            if (znak[it.xx]==znak[p]){
                //x + shift[p] + x + shift[it.xx] = it.yy
                double tx=(double)(it.yy-shift[p]-shift[it.xx])*znak[p]/2;
                if (determined){
                    if (abs(tx-x)>eps) cout<<"NO\n",exit(0);
                }
                else x=tx,determined=true;
            }
            else if (shift[p]+shift[it.xx]!=it.yy)
            {

                cout<<"NO\n",exit(0);
            }
        }
        else
        {
            znak[it.xx]=-znak[p];
            shift[it.xx]=it.yy-shift[p];
            dfs(it.xx);
        }
    }
}

void solve(int root)
{
    poseceni.clear();
    determined=false;
    znak[root]=1,dfs(root);

    if (!determined)
    {
        vector<int> smene;
        for (auto i : poseceni) smene.pb(-znak[i]*shift[i]);
        sort(all(smene));
        int n=(int)smene.size();
        x=smene[n/2];
    }

    for (auto it : poseceni) ans[it]=shift[it]+znak[it]*x;
}

int main()
{
    FAST;

    int n,m; cin>>n>>m;
    while (m--)
    {
        int u,v,w; cin>>u>>v>>w;
        g[u].pb({v,w}),g[v].pb({u,w});
        if (w==1) w1.pb({u,v});
        else w2.pb({u,v});
    }

    fff(i,1,n) if (!znak[i]) solve(i);

    cout<<"YES\n";
    fff(i,1,n) cout<<ans[i]<<" ";
}

//Note to self: Check for overflow

/*

7 12 2
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
2 3 2
3 4 2
4 5 2
5 6 2
6 7 2
7 2 2

8 10
2 7 1
7 8 1
8 6 1
2 3 2
3 6 2
1 2 2
5 6 2
4 3 1
1 4 1
4 5 1

*/

Subtask #1
5.0 / 5.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
17.0 / 17.0

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

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 2 ms 2644 KB answer = YES
3 Correct 2 ms 2656 KB answer = YES
4 Correct 1 ms 2644 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 1 ms 2644 KB answer = YES
7 Correct 2 ms 2644 KB answer = YES
8 Correct 2 ms 2684 KB answer = YES
9 Correct 2 ms 2688 KB answer = NO
10 Correct 2 ms 2644 KB answer = YES
11 Correct 2 ms 2644 KB answer = YES
12 Correct 2 ms 2644 KB answer = NO
13 Correct 2 ms 2692 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 2 ms 2692 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2644 KB answer = YES
18 Correct 2 ms 2644 KB answer = YES
19 Correct 2 ms 2700 KB answer = YES
20 Correct 2 ms 2644 KB answer = YES
21 Correct 2 ms 2644 KB answer = YES
22 Correct 2 ms 2688 KB answer = NO
23 Correct 2 ms 2644 KB answer = NO
24 Correct 2 ms 2688 KB answer = YES
25 Correct 2 ms 2644 KB answer = YES
26 Correct 2 ms 2644 KB answer = YES
27 Correct 2 ms 2644 KB answer = YES
28 Correct 2 ms 2644 KB answer = YES
29 Correct 2 ms 2684 KB answer = YES
30 Correct 2 ms 2644 KB answer = NO
31 Correct 2 ms 2644 KB answer = YES
32 Correct 2 ms 2688 KB answer = YES
33 Correct 2 ms 2644 KB answer = YES
34 Correct 2 ms 2644 KB answer = YES
35 Correct 2 ms 2644 KB answer = YES
36 Correct 2 ms 2772 KB answer = YES
37 Correct 2 ms 2696 KB answer = YES
38 Correct 2 ms 2644 KB answer = YES
39 Correct 2 ms 2644 KB answer = YES
40 Correct 2 ms 2772 KB answer = YES
41 Correct 2 ms 2772 KB answer = NO
42 Correct 2 ms 2772 KB answer = YES
43 Correct 3 ms 2772 KB answer = YES
44 Correct 3 ms 2772 KB answer = YES
45 Correct 2 ms 2772 KB answer = YES
46 Correct 2 ms 2684 KB answer = YES
47 Correct 2 ms 2772 KB answer = YES
48 Correct 3 ms 2772 KB answer = YES
49 Correct 10 ms 3668 KB answer = YES
50 Correct 10 ms 3924 KB answer = YES
51 Correct 10 ms 3924 KB answer = YES
52 Correct 5 ms 3344 KB answer = NO
53 Correct 3 ms 2772 KB answer = YES
54 Correct 4 ms 2900 KB answer = YES
55 Correct 6 ms 3156 KB answer = YES
56 Correct 10 ms 3636 KB answer = YES
57 Correct 10 ms 3540 KB answer = YES
58 Correct 8 ms 3412 KB answer = YES
59 Correct 9 ms 3540 KB answer = YES
60 Correct 9 ms 3596 KB answer = YES
61 Correct 6 ms 3088 KB answer = YES
62 Correct 53 ms 11192 KB answer = NO
63 Correct 62 ms 11812 KB answer = YES
64 Correct 54 ms 11708 KB answer = NO
65 Correct 59 ms 11900 KB answer = YES
66 Correct 3 ms 2772 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 2 ms 2644 KB answer = YES
3 Correct 2 ms 2656 KB answer = YES
4 Correct 1 ms 2644 KB answer = NO
5 Correct 2 ms 2644 KB answer = YES
6 Correct 1 ms 2644 KB answer = YES
7 Correct 2 ms 2644 KB answer = YES
8 Correct 2 ms 2684 KB answer = YES
9 Correct 2 ms 2688 KB answer = NO
10 Correct 2 ms 2644 KB answer = YES
11 Correct 2 ms 2644 KB answer = YES
12 Correct 2 ms 2644 KB answer = NO
13 Correct 2 ms 2692 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 2 ms 2692 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2644 KB answer = YES
18 Correct 2 ms 2644 KB answer = YES
19 Correct 2 ms 2700 KB answer = YES
20 Correct 2 ms 2644 KB answer = YES
21 Correct 2 ms 2644 KB answer = YES
22 Correct 2 ms 2688 KB answer = NO
23 Correct 2 ms 2644 KB answer = NO
24 Correct 2 ms 2688 KB answer = YES
25 Correct 2 ms 2644 KB answer = YES
26 Correct 2 ms 2644 KB answer = YES
27 Correct 2 ms 2644 KB answer = YES
28 Correct 2 ms 2644 KB answer = YES
29 Correct 2 ms 2684 KB answer = YES
30 Correct 2 ms 2644 KB answer = NO
31 Correct 2 ms 2644 KB answer = YES
32 Correct 2 ms 2688 KB answer = YES
33 Correct 2 ms 2644 KB answer = YES
34 Correct 2 ms 2644 KB answer = YES
35 Correct 2 ms 2644 KB answer = YES
36 Correct 2 ms 2772 KB answer = YES
37 Correct 2 ms 2696 KB answer = YES
38 Correct 2 ms 2644 KB answer = YES
39 Correct 2 ms 2644 KB answer = YES
40 Correct 2 ms 2772 KB answer = YES
41 Correct 2 ms 2772 KB answer = NO
42 Correct 2 ms 2772 KB answer = YES
43 Correct 3 ms 2772 KB answer = YES
44 Correct 3 ms 2772 KB answer = YES
45 Correct 2 ms 2772 KB answer = YES
46 Correct 2 ms 2684 KB answer = YES
47 Correct 2 ms 2772 KB answer = YES
48 Correct 3 ms 2772 KB answer = YES
49 Correct 10 ms 3668 KB answer = YES
50 Correct 10 ms 3924 KB answer = YES
51 Correct 10 ms 3924 KB answer = YES
52 Correct 5 ms 3344 KB answer = NO
53 Correct 3 ms 2772 KB answer = YES
54 Correct 4 ms 2900 KB answer = YES
55 Correct 6 ms 3156 KB answer = YES
56 Correct 10 ms 3636 KB answer = YES
57 Correct 10 ms 3540 KB answer = YES
58 Correct 8 ms 3412 KB answer = YES
59 Correct 9 ms 3540 KB answer = YES
60 Correct 9 ms 3596 KB answer = YES
61 Correct 6 ms 3088 KB answer = YES
62 Correct 53 ms 11192 KB answer = NO
63 Correct 62 ms 11812 KB answer = YES
64 Correct 54 ms 11708 KB answer = NO
65 Correct 59 ms 11900 KB answer = YES
66 Correct 3 ms 2772 KB answer = YES
67 Correct 84 ms 17416 KB answer = YES
68 Correct 77 ms 18016 KB answer = YES
69 Correct 74 ms 17644 KB answer = YES
70 Correct 106 ms 22852 KB answer = YES
71 Correct 80 ms 17852 KB answer = YES
72 Correct 105 ms 11640 KB answer = YES
73 Correct 84 ms 11564 KB answer = YES
74 Correct 53 ms 11516 KB answer = YES
75 Correct 30 ms 8492 KB answer = NO
76 Correct 12 ms 3780 KB answer = YES
77 Correct 22 ms 4940 KB answer = YES
78 Correct 39 ms 6580 KB answer = YES
79 Correct 74 ms 10320 KB answer = YES
80 Correct 58 ms 11832 KB answer = YES
81 Correct 41 ms 12476 KB answer = NO
82 Correct 91 ms 16956 KB answer = YES
83 Correct 105 ms 17416 KB answer = YES
84 Correct 104 ms 17356 KB answer = YES
85 Correct 83 ms 17348 KB answer = YES
86 Correct 76 ms 17332 KB answer = YES
87 Correct 51 ms 12252 KB answer = NO
88 Correct 117 ms 13768 KB answer = YES
89 Correct 90 ms 10568 KB answer = YES
90 Correct 89 ms 10580 KB answer = YES
91 Correct 98 ms 10516 KB answer = YES
92 Correct 43 ms 7312 KB answer = YES
93 Correct 42 ms 7108 KB answer = YES
94 Correct 49 ms 15420 KB answer = NO
95 Correct 46 ms 10228 KB answer = NO
96 Correct 162 ms 20536 KB answer = YES
97 Correct 34 ms 15392 KB answer = NO