Submission #342896

#	Time	Username	Problem	Language	Result	Execution time	Memory
342896		leinad2	Graph (BOI20_graph)	C++17	100 / 100	204 ms	24036 KiB

Graph

#include<bits/stdc++.h>
using namespace std;
int n, m, i, j, k, a, b, c, vis[100010], A[100010][2];
vector<pair<int, int> >adj[100010];
double ans[100010];
bool flag=true;
vector<double>V;
vector<int>chk;
void dfs(int v)
{
    chk.push_back(v);
    for(int i=0;i<adj[v].size();i++)
    {
        int p=adj[v][i].first;
        if(!vis[p])
        {
            vis[p]=1;
            A[p][0]=-A[v][0];
            A[p][1]=adj[v][i].second-A[v][1];
            dfs(p);
        }
        else
        {
            if(A[p][0]==A[v][0])
            {
                V.push_back((double)(adj[v][i].second-A[p][1]-A[v][1])/(A[p][0]+A[v][0]));
            }
            else
            {
                if(A[p][1]+A[v][1]!=adj[v][i].second)
                {
                    flag=false;
                }
            }
        }
    }
}
int main()
{
    for(scanf("%d %d", &n, &m);i++<m;)
    {
        scanf("%d %d %d", &a, &b, &c);
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    for(i=0;i++<n;)
    {
        if(!vis[i])
        {
            V.clear();
            chk.clear();
            vis[i]=1;
            A[i][0]=1;
            A[i][1]=0;
            dfs(i);
            if(flag==false)
            {
                puts("NO");
                return 0;
            }
            if(V.size())
            {
                for(j=1;j<V.size();j++)
                {
                    if(V[j]!=V[0])
                    {
                        puts("NO");
                        return 0;
                    }
                }
                for(j=0;j<chk.size();j++)
                {
                    k=chk[j];
                    ans[k]=(double)A[k][0]*V[0]+(double)A[k][1];
                }
            }
            else
            {
                vector<int>v;
                for(j=0;j<chk.size();j++)
                {
                    k=chk[j];
                    v.push_back(-(A[k][1]/A[k][0]));
                }
                sort(v.begin(), v.end());
                double a=(double)(v[v.size()/2]);
                for(j=0;j<chk.size();j++)
                {
                    k=chk[j];
                    ans[k]=a*(double)A[k][0]+(double)A[k][1];
                }
            }
        }
    }
    puts("YES");
    for(i=0;i++<n;)printf("%.10lf ", ans[i]);
}

Compilation message (stderr)

Graph.cpp: In function 'void dfs(int)':
Graph.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i=0;i<adj[v].size();i++)
      |                 ~^~~~~~~~~~~~~~
Graph.cpp: In function 'int main()':
Graph.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |                 for(j=1;j<V.size();j++)
      |                         ~^~~~~~~~~
Graph.cpp:71:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |                 for(j=0;j<chk.size();j++)
      |                         ~^~~~~~~~~~~
Graph.cpp:80:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |                 for(j=0;j<chk.size();j++)
      |                         ~^~~~~~~~~~~
Graph.cpp:87:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |                 for(j=0;j<chk.size();j++)
      |                         ~^~~~~~~~~~~
Graph.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |     for(scanf("%d %d", &n, &m);i++<m;)
      |         ~~~~~^~~~~~~~~~~~~~~~~
Graph.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |         scanf("%d %d %d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 42 / 42