oj.uz

Submission #1107964

# Submission time Handle Problem Language Result Execution time Memory
1107964 2024-11-02T13:08:10 Z simona1230 Graph (BOI20_graph) C++17
5 / 100
 700 ms 3832 KB 
#include <bits/stdc++.h>

using namespace std;
int n,m;
vector<pair<int,double> > v[100001];

void read()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }
}

vector<int> curr;
double sum,ans;
int pos;
double c[200001];
int used[200001];

const double minn=0.0000001;

void dfs(int i)
{
    //cout<<i<<" "<<c[i]<<endl;
    used[i]=1;
    curr.push_back(i);
    sum+=abs(c[i]);
    for(int j=0; j<v[i].size(); j++)
    {
        pair<int,int> nb=v[i][j];
        int x=nb.first;
        double y=nb.second;
        double diff=c[x]+c[i]-y;
        if(used[x]&&(diff>=minn||diff<=-minn))
        {
            //cout<<i<<" x "<<x<<" "<<c[x]+c[i]<<" "<<y<<endl;
            pos=0;
        }
        else if(!used[x])
        {
            if(y==c[i])c[x]=0;
            else
            {
                if(y-c[i]<minn&&y-c[i]>-minn)c[x]=0;
                else c[x]=y-c[i];
            }
            dfs(x);
        }
    }
}

double f[100001];

void try_(int i,double val)
{
    //cout<<endl;
    for(int j=0; j<curr.size(); j++)
    {
        used[curr[j]]=0;
    }

    curr.clear();
    //cout<<val<<endl;
    pos=1;
    sum=0;
    c[i]=val;

    dfs(i);

    if(pos&&sum<ans)ans=sum;
    //cout<<sum<<" "<<ans<<" "<<pos<<endl;
    for(int j=0; j<curr.size(); j++)
    {
        double diff=ans-sum;
        if(diff>-minn&&diff<minn&&pos)f[curr[j]]=c[curr[j]];
    }
}

void solve()
{
    for(int i=1; i<=n; i++)
    {
        if(!used[i])

        {
            ans=100000;
            double x=0.000001;
            for(double val=-2;val<0;val=val+x)
            {
                try_(i,val);
            }

            try_(i,0);

            for(double val=0.000001;val<=2;val=val+x)
            {
                try_(i,val);
            }


            if(ans==100000)
            {
                cout<<"NO"<<endl;
                exit(0);
            }
        }
    }

    //cout<<ans<<endl;
    cout<<"YES"<<endl;
    for(int i=1; i<=n; i++)
        cout<<fixed<<setprecision(7)<<f[i]<<" ";
    cout<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    read();
    solve();
    return 0;
}

Compilation message

Graph.cpp: In function 'void dfs(int)':
Graph.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int j=0; j<v[i].size(); j++)
      |                  ~^~~~~~~~~~~~
Graph.cpp: In function 'void try_(int, double)':
Graph.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int j=0; j<curr.size(); j++)
      |                  ~^~~~~~~~~~~~
Graph.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int j=0; j<curr.size(); j++)
      |                  ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 3664 KB answer = YES
2 Correct 80 ms 3664 KB answer = YES
3 Correct 118 ms 3664 KB answer = YES
4 Correct 132 ms 3664 KB answer = NO
5 Correct 274 ms 3832 KB answer = YES
6 Correct 117 ms 3664 KB answer = YES
7 Correct 136 ms 3664 KB answer = YES
8 Correct 189 ms 3716 KB answer = YES
9 Correct 170 ms 3664 KB answer = NO
10 Correct 195 ms 3664 KB answer = YES
11 Correct 205 ms 3664 KB answer = YES
12 Correct 180 ms 3664 KB answer = NO
13 Correct 380 ms 3704 KB answer = YES
14 Correct 211 ms 3832 KB answer = YES
15 Correct 196 ms 3664 KB answer = YES
16 Correct 208 ms 3664 KB answer = YES
17 Correct 39 ms 3664 KB answer = YES
18 Correct 53 ms 3664 KB answer = YES
19 Correct 364 ms 3704 KB answer = YES
20 Correct 147 ms 3664 KB answer = YES
21 Correct 100 ms 3664 KB answer = YES
22 Correct 93 ms 3832 KB answer = NO
23 Correct 350 ms 3664 KB answer = NO

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 3664 KB answer = YES
2 Correct 80 ms 3664 KB answer = YES
3 Correct 118 ms 3664 KB answer = YES
4 Correct 132 ms 3664 KB answer = NO
5 Correct 274 ms 3832 KB answer = YES
6 Correct 117 ms 3664 KB answer = YES
7 Correct 136 ms 3664 KB answer = YES
8 Correct 189 ms 3716 KB answer = YES
9 Correct 170 ms 3664 KB answer = NO
10 Correct 195 ms 3664 KB answer = YES
11 Correct 205 ms 3664 KB answer = YES
12 Correct 180 ms 3664 KB answer = NO
13 Correct 380 ms 3704 KB answer = YES
14 Correct 211 ms 3832 KB answer = YES
15 Correct 196 ms 3664 KB answer = YES
16 Correct 208 ms 3664 KB answer = YES
17 Correct 39 ms 3664 KB answer = YES
18 Correct 53 ms 3664 KB answer = YES
19 Correct 364 ms 3704 KB answer = YES
20 Correct 147 ms 3664 KB answer = YES
21 Correct 100 ms 3664 KB answer = YES
22 Correct 93 ms 3832 KB answer = NO
23 Correct 350 ms 3664 KB answer = NO
24 Execution timed out 1056 ms 3664 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 3664 KB answer = YES
2 Correct 80 ms 3664 KB answer = YES
3 Correct 118 ms 3664 KB answer = YES
4 Correct 132 ms 3664 KB answer = NO
5 Correct 274 ms 3832 KB answer = YES
6 Correct 117 ms 3664 KB answer = YES
7 Correct 136 ms 3664 KB answer = YES
8 Correct 189 ms 3716 KB answer = YES
9 Correct 170 ms 3664 KB answer = NO
10 Correct 195 ms 3664 KB answer = YES
11 Correct 205 ms 3664 KB answer = YES
12 Correct 180 ms 3664 KB answer = NO
13 Correct 380 ms 3704 KB answer = YES
14 Correct 211 ms 3832 KB answer = YES
15 Correct 196 ms 3664 KB answer = YES
16 Correct 208 ms 3664 KB answer = YES
17 Correct 39 ms 3664 KB answer = YES
18 Correct 53 ms 3664 KB answer = YES
19 Correct 364 ms 3704 KB answer = YES
20 Correct 147 ms 3664 KB answer = YES
21 Correct 100 ms 3664 KB answer = YES
22 Correct 93 ms 3832 KB answer = NO
23 Correct 350 ms 3664 KB answer = NO
24 Execution timed out 1056 ms 3664 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 3664 KB answer = YES
2 Correct 80 ms 3664 KB answer = YES
3 Correct 118 ms 3664 KB answer = YES
4 Correct 132 ms 3664 KB answer = NO
5 Correct 274 ms 3832 KB answer = YES
6 Correct 117 ms 3664 KB answer = YES
7 Correct 136 ms 3664 KB answer = YES
8 Correct 189 ms 3716 KB answer = YES
9 Correct 170 ms 3664 KB answer = NO
10 Correct 195 ms 3664 KB answer = YES
11 Correct 205 ms 3664 KB answer = YES
12 Correct 180 ms 3664 KB answer = NO
13 Correct 380 ms 3704 KB answer = YES
14 Correct 211 ms 3832 KB answer = YES
15 Correct 196 ms 3664 KB answer = YES
16 Correct 208 ms 3664 KB answer = YES
17 Correct 39 ms 3664 KB answer = YES
18 Correct 53 ms 3664 KB answer = YES
19 Correct 364 ms 3704 KB answer = YES
20 Correct 147 ms 3664 KB answer = YES
21 Correct 100 ms 3664 KB answer = YES
22 Correct 93 ms 3832 KB answer = NO
23 Correct 350 ms 3664 KB answer = NO
24 Execution timed out 1056 ms 3664 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 3664 KB answer = YES
2 Correct 80 ms 3664 KB answer = YES
3 Correct 118 ms 3664 KB answer = YES
4 Correct 132 ms 3664 KB answer = NO
5 Correct 274 ms 3832 KB answer = YES
6 Correct 117 ms 3664 KB answer = YES
7 Correct 136 ms 3664 KB answer = YES
8 Correct 189 ms 3716 KB answer = YES
9 Correct 170 ms 3664 KB answer = NO
10 Correct 195 ms 3664 KB answer = YES
11 Correct 205 ms 3664 KB answer = YES
12 Correct 180 ms 3664 KB answer = NO
13 Correct 380 ms 3704 KB answer = YES
14 Correct 211 ms 3832 KB answer = YES
15 Correct 196 ms 3664 KB answer = YES
16 Correct 208 ms 3664 KB answer = YES
17 Correct 39 ms 3664 KB answer = YES
18 Correct 53 ms 3664 KB answer = YES
19 Correct 364 ms 3704 KB answer = YES
20 Correct 147 ms 3664 KB answer = YES
21 Correct 100 ms 3664 KB answer = YES
22 Correct 93 ms 3832 KB answer = NO
23 Correct 350 ms 3664 KB answer = NO
24 Execution timed out 1056 ms 3664 KB Time limit exceeded
25 Halted 0 ms 0 KB -