Submission #1003431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003431		ibm2006	Utrka (COCI14_utrka)	C++17	0 / 80	2 ms	3672 KiB

utrka

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll inf=1e9;
ll n,m,i,j,k,l,r,x,y,z,w,s,t,dp[110000],h[110000],d[110000];
pair<ll,ll> p[110000];
queue<ll> q;
vector<pair<ll,ll>> v[110000];
int main()
{
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d %d",&x,&y,&z,&w);
        p[i]={x,y};
        d[i]={w-z};
    }
    for(i=0;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            v[i*(n+1)+p[j].first].push_back({(i+1)*(n+1)+p[j].second,d[j]});
            h[(i+1)*(n+1)+p[j].second]++;
        }
    }
    for(i=1;i<=100000;i++)
    {
        dp[i]=-inf;
    }
    dp[1]=0;
    for(i=1;i<=100000;i++)
    {
        if(h[i]==0)
            q.push(i);
    }
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        for(i=0;i<v[x].size();i++)
        {
           // printf("[%lld]",v[x][i].first);
            y=v[x][i].first;
            z=v[x][i].second;
            dp[y]=max(dp[y],dp[x]+z);
            h[y]--;
            if(h[y]==0)
                q.push(y);
        }
    }
    for(i=1;i<=n;i++)
    {//printf("(%lld)\n",dp[(n+1)*i+1]);
        if(dp[(n+1)*i+1]>0)
        {

            printf("%d %d",i,dp[(n+1)*i+1]);
            return 0;
        }
    }
}

Compilation message (stderr)

utrka.cpp: In function 'int main()':
utrka.cpp:40:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(i=0;i<v[x].size();i++)
      |                 ~^~~~~~~~~~~~
utrka.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
utrka.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         scanf("%d %d %d %d",&x,&y,&z,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 80