oj.uz

Submission #932230

# Submission time Handle Problem Language Result Execution time Memory
932230 2024-02-23T05:57:13 Z Faisal_Saqib Graph (BOI20_graph) C++17
34 / 100
 700 ms 2224 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
#define ld long double
vector<pair<int,int>> ma[N];
int h[N],pre[N];
bool vis[N];
vector<pair<int,ld>> pos;
set<int> anc;
double val[N],sum[N],fin[N];
bool flip[N],posa[N];
void dfs(int x,int p=-1)
{
    vis[x]=1;
    cout<<"Parent "<<p<<' '<<x<<endl;
    if(p==-1)
    {
        h[x]=0;
    }
    else{
        h[x]=(h[p]+1)%2;
    }
    vis[x]=1;
    anc.insert(x);
    for(auto [y,w]:ma[x])
    {
        if(y!=p)
        {
            if(vis[y] and anc.find(y)!=anc.end())
            {
                // Cylce
                // WE 
                // a[1]->a[2]->a[3]->a[4]
                //a[1]+a[2]==pre[2]
                // a[1]+a[2]+a[2]+a[3]=pre[3]
                // a[1]+a[2]+a[2]+a[3]+a[3]+a[4]=pre[4]
                // a[3]+a[4]=w
                // pre[4]-w
                cout<<"Hola Cycle "<<x<<' '<<y<<endl;
                if((h[y]==h[x]))
                {
                    if(h[x]==1)
                    {
                        ld p=pre[y]-pre[x];
                        ld q=w;
                        pos.push_back({y,(p+q)/2.0});
                    }
                    else{
                        ld p=pre[x];
                        ld q=w;
                        pos.push_back({y,(p+q)/2.0});
                    }
                }
            }
            else{
                if(h[x]==0)
                {
                    pre[y]=pre[x]+w;
                }
                else{
                    pre[y]=pre[x]-w;
                }
                dfs(y,x);
            }
        }
    }
    anc.erase(x);
}
bool check(int x,double vl)
{
    // cout<<"For vertex "<<x<<" then it is "<<vl<<endl;
    vis[x]=1;
    flip[x]=1;
    val[x]=vl;
    for(auto [y,w]:ma[x])
    {
        if(!vis[y])
        {
            flip[x]&=check(y,w-vl);
        }
        else if((val[y])!=(w-val[x]))
        {
            flip[x]=0;
        }
        else
        {
            flip[x]&=flip[y];
        }
    }
    return flip[x];
}
int part[N];
void init(int n)
{
    for(int i=1;i<=n;i++)
        part[i]=i;
}
int root(int x)
{
    return ((part[x]==x)?x:part[x]=root(part[x]));
}
vector<int> cms[N];
void join(int x,int y)
{
    x=root(x);
    y=root(y);
    if(x!=y)
    {
        part[x]=y;
    }
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        sum[i]=1e9;
    }
    init(n);
    for(int j=0;j<m;j++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        join(a,b);
        ma[a].push_back({b,c});
        ma[b].push_back({a,c});
    }
    for(int i=1;i<=n;i++)
        cms[root(i)].push_back(i);
    for(int i=1;i<=n;i++)
    {    
        if(!posa[root(i)])
        {            
            for(double vl=-5;vl<=5;vl+=0.5)
            {
                // for(int j=1;j<=n;j++)
                // {
                //     vis[j]=0;
                // }
                for(auto j:cms[root(i)])
                    vis[j]=0;
                if(check(i,vl))
                {
                    // cout<<"Can place values\n";
                    double dp=0;
                    for(auto j:cms[root(i)])
                        dp+=abs(val[j]);
                    // cout<<"Done sum = "<<dp<<endl;
                    if(dp<sum[root(i)])
                    {
                        posa[root(i)]=1;
                        for(auto j:cms[root(i)])
                            fin[j]=val[j];
                        sum[root(i)]=dp;
                    }
                }
            }
        }
    }
    bool pos=1;
    for(int i=1;i<=n;i++)
    {
        pos&=(posa[root(i)]);
    }
    if(pos)
    {
        cout<<"YES\n";
        for(int i=1;i<=n;i++)
        {
            cout<<fin[i]<<' ';
        }
        cout<<endl;
    }
    else{
        cout<<"NO\n";
    }
    return 0;
}
/*
 
a[4]+a[1]
a[1]+a[2]
a[2]+a[3]
 
 
a[4]+a[3]
// a[3]-a[1]
// a[1]-a[3] == p
// a[1]+a[3] == q
// a[1] == (p+q)/2
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
17.0 / 17.0

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

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB answer = YES
2 Correct 0 ms 860 KB answer = YES
3 Correct 1 ms 860 KB answer = YES
4 Correct 1 ms 860 KB answer = NO
5 Correct 1 ms 860 KB answer = YES
6 Correct 1 ms 860 KB answer = YES
7 Correct 1 ms 856 KB answer = YES
8 Correct 1 ms 860 KB answer = YES
9 Correct 0 ms 860 KB answer = NO
10 Correct 0 ms 860 KB answer = YES
11 Correct 0 ms 1112 KB answer = YES
12 Correct 1 ms 860 KB answer = NO
13 Correct 1 ms 856 KB answer = YES
14 Correct 0 ms 860 KB answer = YES
15 Correct 0 ms 860 KB answer = YES
16 Correct 0 ms 860 KB answer = YES
17 Correct 1 ms 860 KB answer = YES
18 Correct 1 ms 860 KB answer = YES
19 Correct 0 ms 860 KB answer = YES
20 Correct 1 ms 860 KB answer = YES
21 Correct 1 ms 860 KB answer = YES
22 Correct 1 ms 908 KB answer = NO
23 Correct 0 ms 860 KB answer = NO
24 Correct 1 ms 860 KB answer = YES
25 Correct 1 ms 860 KB answer = YES
26 Correct 1 ms 860 KB answer = YES
27 Correct 1 ms 860 KB answer = YES
28 Correct 1 ms 860 KB answer = YES
29 Correct 1 ms 860 KB answer = YES
30 Correct 2 ms 860 KB answer = NO
31 Correct 0 ms 860 KB answer = YES
32 Correct 1 ms 856 KB answer = YES
33 Correct 1 ms 860 KB answer = YES
34 Correct 1 ms 860 KB answer = YES
35 Correct 1 ms 860 KB answer = YES
36 Correct 1 ms 860 KB answer = YES
37 Correct 1 ms 860 KB answer = YES
38 Correct 1 ms 860 KB answer = YES
39 Correct 1 ms 860 KB answer = YES
40 Correct 2 ms 860 KB answer = YES
41 Correct 201 ms 1036 KB answer = NO
42 Correct 2 ms 860 KB answer = YES
43 Correct 1 ms 784 KB answer = YES
44 Correct 1 ms 860 KB answer = YES
45 Correct 1 ms 860 KB answer = YES
46 Correct 1 ms 860 KB answer = YES
47 Correct 1 ms 856 KB answer = YES
48 Correct 1 ms 860 KB answer = YES
49 Correct 11 ms 1628 KB answer = YES
50 Correct 24 ms 2136 KB answer = YES
51 Correct 11 ms 1884 KB answer = YES
52 Execution timed out 1044 ms 2224 KB Time limit exceeded
53 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB answer = YES
2 Correct 0 ms 860 KB answer = YES
3 Correct 1 ms 860 KB answer = YES
4 Correct 1 ms 860 KB answer = NO
5 Correct 1 ms 860 KB answer = YES
6 Correct 1 ms 860 KB answer = YES
7 Correct 1 ms 856 KB answer = YES
8 Correct 1 ms 860 KB answer = YES
9 Correct 0 ms 860 KB answer = NO
10 Correct 0 ms 860 KB answer = YES
11 Correct 0 ms 1112 KB answer = YES
12 Correct 1 ms 860 KB answer = NO
13 Correct 1 ms 856 KB answer = YES
14 Correct 0 ms 860 KB answer = YES
15 Correct 0 ms 860 KB answer = YES
16 Correct 0 ms 860 KB answer = YES
17 Correct 1 ms 860 KB answer = YES
18 Correct 1 ms 860 KB answer = YES
19 Correct 0 ms 860 KB answer = YES
20 Correct 1 ms 860 KB answer = YES
21 Correct 1 ms 860 KB answer = YES
22 Correct 1 ms 908 KB answer = NO
23 Correct 0 ms 860 KB answer = NO
24 Correct 1 ms 860 KB answer = YES
25 Correct 1 ms 860 KB answer = YES
26 Correct 1 ms 860 KB answer = YES
27 Correct 1 ms 860 KB answer = YES
28 Correct 1 ms 860 KB answer = YES
29 Correct 1 ms 860 KB answer = YES
30 Correct 2 ms 860 KB answer = NO
31 Correct 0 ms 860 KB answer = YES
32 Correct 1 ms 856 KB answer = YES
33 Correct 1 ms 860 KB answer = YES
34 Correct 1 ms 860 KB answer = YES
35 Correct 1 ms 860 KB answer = YES
36 Correct 1 ms 860 KB answer = YES
37 Correct 1 ms 860 KB answer = YES
38 Correct 1 ms 860 KB answer = YES
39 Correct 1 ms 860 KB answer = YES
40 Correct 2 ms 860 KB answer = YES
41 Correct 201 ms 1036 KB answer = NO
42 Correct 2 ms 860 KB answer = YES
43 Correct 1 ms 784 KB answer = YES
44 Correct 1 ms 860 KB answer = YES
45 Correct 1 ms 860 KB answer = YES
46 Correct 1 ms 860 KB answer = YES
47 Correct 1 ms 856 KB answer = YES
48 Correct 1 ms 860 KB answer = YES
49 Correct 11 ms 1628 KB answer = YES
50 Correct 24 ms 2136 KB answer = YES
51 Correct 11 ms 1884 KB answer = YES
52 Execution timed out 1044 ms 2224 KB Time limit exceeded
53 Halted 0 ms 0 KB -