oj.uz

Submission #1049493

# Submission time Handle Problem Language Result Execution time Memory
1049493 2024-08-08T19:36:30 Z Ludissey Graph (BOI20_graph) C++17
58 / 100
 493 ms 36448 KB 
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
 
using namespace std;
 
vector<vector<int>> neigh1;
vector<vector<int>> neigh2;
vector<int> sz;
vector<int> visited;
vector<int> parent;
vector<int> eqCOLOR;
 
bool no=false;
 
int getParent(int a){
    return (a==parent[a]) ? a : parent[a]=getParent(parent[a]); 
}
 
void unite(int a, int b){
    a=getParent(a); b=getParent(b);
    if(a==b) return;
    if(sz[a]<sz[b]) swap(a,b);
    sz[a]+=sz[b];
    parent[b]=a;
}
 
vector<vector<pair<int,int>>> neigh;
 
void dfs(int x, int c){
    eqCOLOR[x]=c;
    visited[x]=true;
    for (int i=0; i<sz(neigh[x]); i++)
    {
        pair<int,int> u=neigh[x][i];
        if(eqCOLOR[u.first]!=-1&&eqCOLOR[u.first]!=(u.second*2)-c) no=true;
        if(visited[u.first]) continue;
        dfs(u.first,(u.second*2)-c);
    }
}
 
int colorCOUNT(int x){
    int sm=abs(eqCOLOR[x])*sz[x];
    visited[x]=false;
    eqCOLOR[x]=-1;
    for (int i=0; i<sz(neigh[x]); i++)
    {
        pair<int,int> u=neigh[x][i];
        if(!visited[u.first]) continue;
        sm+=colorCOUNT(u.first);
    }
    return sm;
}
 
signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N,M; cin >> N >> M;
    neigh1.resize(N);
    sz.resize(N,1);
    parent.resize(N,1);
    eqCOLOR.resize(N,-1);
    neigh2.resize(N);
    vector<pair<pair<int,int>,int>> ed(M);
    for (int i = 0; i < N; i++) parent[i]=i;
    
    for (int i = 0; i < M; i++)
    {
        int a,b,c; cin >> a >> b >> c;
        a--;
        b--;
        if(c==1){
            neigh1[a].push_back(b);
            neigh1[b].push_back(a);
        }else{
            neigh2[a].push_back(b);
            neigh2[b].push_back(a);
        }
        ed[i]={{a,b},c};
    }
    for (int i = 0; i < N; i++){
        for (int j = 1; j < sz(neigh1[i]); j++)  unite(neigh1[i][j-1],neigh1[i][j]);
        for (int j = 1; j < sz(neigh2[i]); j++)  unite(neigh2[i][j-1],neigh2[i][j]);
    }
    unordered_map<int,int> mp;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < sz(neigh1[i]); j++) mp[getParent(neigh1[i][j])]=i+1;
        for (int j = 0; j < sz(neigh2[i]); j++) {
            if(mp[getParent(neigh2[i][j])]==i+1) {
                cout << "NO\n";
                return 0;
            }
        }
    }
    for (int i = 0; i < N; i++){
        for (int j = 0; j < sz(neigh1[i]); j++) {
            if(getParent(i)==getParent(neigh1[i][j])) {
                if(eqCOLOR[getParent(i)]==2){
                    cout << "NO\n";
                    return 0;
                } 
                eqCOLOR[getParent(i)]=1;
            }
        }
        for (int j = 0; j < sz(neigh2[i]); j++) {
            if(getParent(i)==getParent(neigh2[i][j])) {
                if(eqCOLOR[getParent(i)]==1) {
                    cout << "NO\n";
                    return 0;
                }
                eqCOLOR[getParent(i)]=2;
            }
        }
    }
    vector<set<pair<int,int>>> neighCOPY(N);
    neigh.resize(N);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < sz(neigh1[i]); j++) {
            if(getParent(i)!=getParent(neigh1[i][j])) neighCOPY[getParent(i)].insert({getParent(neigh1[i][j]),1});
        }  
        for (int j = 0; j < sz(neigh2[i]); j++) {
            if(getParent(i)!=getParent(neigh2[i][j])) neighCOPY[getParent(i)].insert({getParent(neigh2[i][j]),2});
        }
    }
    for (int i = 0; i < N; i++)
    {
        for (auto u : neighCOPY[i])
        {
            neigh[i].push_back(u);
        }
        
    }
    
    visited.resize(N,false);
    unordered_set<int> st;
    for (int i = 0; i < N; i++) st.insert(getParent(i));
    for (auto j : st){
        if(!visited[j]&&eqCOLOR[j]>0) dfs(j,eqCOLOR[j]);
    }
    if(no) { cout << "NO\n"; return 0; }
     for (auto j : st){
        if(!visited[j]){
            if(sz(neigh[j])==0) dfs(j,0); // securite
            else{
                int mn=1e9,mnI=0;
                for (int k = -75; k <= 75; k++) // sinon binary 
                { 
                    dfs(j,k);
                    int c=colorCOUNT(j);
                    if(no) { no=false; continue; }
                    if(c<mn) { mn=c; mnI=k; } 
                }
                dfs(j,mnI);
            }
        }
    }
    for (int i = 0; i < M; i++)
    {
        if(eqCOLOR[getParent(ed[i].first.first)]+eqCOLOR[getParent(ed[i].first.second)]!=ed[i].second*2) no=true;
    }
    
    if(no){
        cout << "NO\n";
    }else{
        cout << "YES\n";
        for (int i = 0; i < N; i++)
        {
            cout << (double)(eqCOLOR[getParent(i)])/2<<" ";
        }
        
    }
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
17.0 / 17.0

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

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB answer = YES
2 Correct 0 ms 348 KB answer = YES
3 Correct 1 ms 612 KB answer = YES
4 Correct 0 ms 348 KB answer = NO
5 Correct 0 ms 348 KB answer = YES
6 Correct 0 ms 348 KB answer = YES
7 Correct 0 ms 600 KB answer = YES
8 Correct 0 ms 348 KB answer = YES
9 Correct 0 ms 348 KB answer = NO
10 Correct 0 ms 348 KB answer = YES
11 Correct 0 ms 348 KB answer = YES
12 Correct 0 ms 344 KB answer = NO
13 Correct 1 ms 344 KB answer = YES
14 Correct 0 ms 348 KB answer = YES
15 Correct 0 ms 348 KB answer = YES
16 Correct 0 ms 348 KB answer = YES
17 Correct 0 ms 348 KB answer = YES
18 Correct 0 ms 348 KB answer = YES
19 Correct 0 ms 348 KB answer = YES
20 Correct 0 ms 348 KB answer = YES
21 Correct 0 ms 348 KB answer = YES
22 Correct 0 ms 348 KB answer = NO
23 Correct 0 ms 348 KB answer = NO
24 Correct 0 ms 348 KB answer = YES
25 Correct 0 ms 348 KB answer = YES
26 Correct 1 ms 344 KB answer = YES
27 Correct 1 ms 348 KB answer = YES
28 Correct 0 ms 348 KB answer = YES
29 Correct 1 ms 348 KB answer = YES
30 Correct 0 ms 348 KB answer = NO
31 Correct 1 ms 344 KB answer = YES
32 Correct 0 ms 348 KB answer = YES
33 Correct 0 ms 348 KB answer = YES
34 Correct 0 ms 348 KB answer = YES
35 Correct 0 ms 344 KB answer = YES
36 Correct 0 ms 344 KB answer = YES
37 Correct 1 ms 348 KB answer = YES
38 Correct 0 ms 348 KB answer = YES
39 Correct 1 ms 348 KB answer = YES
40 Correct 2 ms 604 KB answer = YES
41 Correct 2 ms 604 KB answer = NO
42 Correct 2 ms 604 KB answer = YES
43 Correct 2 ms 604 KB answer = YES
44 Correct 2 ms 604 KB answer = YES
45 Correct 1 ms 604 KB answer = YES
46 Correct 1 ms 348 KB answer = YES
47 Correct 1 ms 604 KB answer = YES
48 Correct 1 ms 748 KB answer = YES
49 Correct 18 ms 3080 KB answer = YES
50 Correct 9 ms 3420 KB answer = YES
51 Correct 33 ms 3492 KB answer = YES
52 Correct 33 ms 3420 KB answer = NO
53 Correct 1 ms 604 KB answer = YES
54 Correct 4 ms 892 KB answer = YES
55 Correct 8 ms 1628 KB answer = YES
56 Correct 18 ms 3008 KB answer = YES
57 Correct 15 ms 2904 KB answer = YES
58 Correct 15 ms 2652 KB answer = YES
59 Correct 7 ms 2652 KB answer = YES
60 Correct 17 ms 2880 KB answer = YES
61 Correct 4 ms 1628 KB answer = YES
62 Correct 38 ms 5884 KB answer = NO
63 Correct 40 ms 6228 KB answer = YES
64 Correct 32 ms 5464 KB answer = NO
65 Correct 40 ms 6224 KB answer = YES
66 Correct 3 ms 856 KB answer = YES

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB answer = YES
2 Correct 0 ms 348 KB answer = YES
3 Correct 1 ms 612 KB answer = YES
4 Correct 0 ms 348 KB answer = NO
5 Correct 0 ms 348 KB answer = YES
6 Correct 0 ms 348 KB answer = YES
7 Correct 0 ms 600 KB answer = YES
8 Correct 0 ms 348 KB answer = YES
9 Correct 0 ms 348 KB answer = NO
10 Correct 0 ms 348 KB answer = YES
11 Correct 0 ms 348 KB answer = YES
12 Correct 0 ms 344 KB answer = NO
13 Correct 1 ms 344 KB answer = YES
14 Correct 0 ms 348 KB answer = YES
15 Correct 0 ms 348 KB answer = YES
16 Correct 0 ms 348 KB answer = YES
17 Correct 0 ms 348 KB answer = YES
18 Correct 0 ms 348 KB answer = YES
19 Correct 0 ms 348 KB answer = YES
20 Correct 0 ms 348 KB answer = YES
21 Correct 0 ms 348 KB answer = YES
22 Correct 0 ms 348 KB answer = NO
23 Correct 0 ms 348 KB answer = NO
24 Correct 0 ms 348 KB answer = YES
25 Correct 0 ms 348 KB answer = YES
26 Correct 1 ms 344 KB answer = YES
27 Correct 1 ms 348 KB answer = YES
28 Correct 0 ms 348 KB answer = YES
29 Correct 1 ms 348 KB answer = YES
30 Correct 0 ms 348 KB answer = NO
31 Correct 1 ms 344 KB answer = YES
32 Correct 0 ms 348 KB answer = YES
33 Correct 0 ms 348 KB answer = YES
34 Correct 0 ms 348 KB answer = YES
35 Correct 0 ms 344 KB answer = YES
36 Correct 0 ms 344 KB answer = YES
37 Correct 1 ms 348 KB answer = YES
38 Correct 0 ms 348 KB answer = YES
39 Correct 1 ms 348 KB answer = YES
40 Correct 2 ms 604 KB answer = YES
41 Correct 2 ms 604 KB answer = NO
42 Correct 2 ms 604 KB answer = YES
43 Correct 2 ms 604 KB answer = YES
44 Correct 2 ms 604 KB answer = YES
45 Correct 1 ms 604 KB answer = YES
46 Correct 1 ms 348 KB answer = YES
47 Correct 1 ms 604 KB answer = YES
48 Correct 1 ms 748 KB answer = YES
49 Correct 18 ms 3080 KB answer = YES
50 Correct 9 ms 3420 KB answer = YES
51 Correct 33 ms 3492 KB answer = YES
52 Correct 33 ms 3420 KB answer = NO
53 Correct 1 ms 604 KB answer = YES
54 Correct 4 ms 892 KB answer = YES
55 Correct 8 ms 1628 KB answer = YES
56 Correct 18 ms 3008 KB answer = YES
57 Correct 15 ms 2904 KB answer = YES
58 Correct 15 ms 2652 KB answer = YES
59 Correct 7 ms 2652 KB answer = YES
60 Correct 17 ms 2880 KB answer = YES
61 Correct 4 ms 1628 KB answer = YES
62 Correct 38 ms 5884 KB answer = NO
63 Correct 40 ms 6228 KB answer = YES
64 Correct 32 ms 5464 KB answer = NO
65 Correct 40 ms 6224 KB answer = YES
66 Correct 3 ms 856 KB answer = YES
67 Correct 227 ms 32352 KB answer = YES
68 Correct 45 ms 18004 KB answer = YES
69 Correct 191 ms 36192 KB answer = YES
70 Correct 66 ms 20788 KB answer = YES
71 Correct 186 ms 36448 KB answer = YES
72 Correct 370 ms 26264 KB answer = YES
73 Correct 337 ms 27408 KB answer = YES
74 Correct 62 ms 21360 KB answer = YES
75 Correct 467 ms 21288 KB answer = NO
76 Correct 28 ms 3676 KB answer = YES
77 Correct 68 ms 7144 KB answer = YES
78 Correct 144 ms 12388 KB answer = YES
79 Correct 285 ms 23416 KB answer = YES
80 Incorrect 493 ms 21936 KB participant answer is larger than the answer of jury
81 Halted 0 ms 0 KB -