Submission #1107578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107578		modwwe	Designated Cities (JOI19_designated_cities)	C++17	23 / 100	18 ms	63824 KiB

designated_cities

#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC optimize("conserve-stack")
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define mask(i) (1<<i)
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar

inline int scan()
{
    char c = getchar_unlocked();
    int x = 0;
    while (c < '0' || c > '9')
    {
        c = getchar_unlocked();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + c - '0';
        c = getchar_unlocked();
    }
    return x;
};
void phongbeo();
const int inf = 1e18;
const int mod2 = -1e9+7;
const int  mod1 = 998244353;
const int base=67;
int add(int x,int y)
{
    if(x+y>=mod2) x-=mod2;
    if(x+y<0) x+=mod2;
    return x+y;
}
struct icd
{
  int c,d;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a, b, c;
};
struct id{
int a,b,c,d;
};
struct ie
{
    int a, b, c, d, e;

};

int  n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int  i, s10, s12,k1,k2,k3,s11,limit,w,l,r,last,root,cost;
int kk;
int el = 19;

main()
{
    if(fopen(task".inp","r"))
    {
        fin(task);
        fou(task);
    }
    NHP
    /// cin>>s1;
    // modwwe
    phongbeo(),down
    // checktime
}

namespace sub4
{int dp[2001][2001][2];
int par[2001];
int sz[2001];
id a[2001];
icd c[2001];
vector<int> v[2001];
void dfs(int x,int y)
 {
par[x]=y;
     for(auto f:v[x])
      if(f!=y)
         dfs(f,x);
 }
 void dfs2(int x,int y)
  {
dp[x][0][0]=0;
sz[x]=0;
        for(auto f:v[x])
            if(f!=y)
            {
                dfs2(f,x);
             for(int i=0;i<=sz[x];i++)
                for(int j=0;j<2;j++)
                dp[x][i][j]+=dp[f][0][0]+c[f].c;
                /// ko add them con gi ca
             for(int i=0;i<=sz[f];i++)
                dp[x][i][1]=min(dp[x][i][1],dp[x][0][0]-dp[f][0][0]-c[f].c+dp[f][i][1]+c[f].d);///end at son of x no add in x
            ///knapsex
             for(int i=sz[x];i>=0;i--)
             for(int j=0;j<=sz[f];j++){
             dp[x][i+j][0]=min(dp[x][i+j][0],dp[x][i][0]-dp[f][0][0]-c[f].c+dp[f][j][0]+(j==0)*c[f].c);
             if(i>0&&j>0)
             dp[x][i+j][1]=min(dp[x][i+j][1],dp[x][i][0]-dp[f][0][0]-c[f].c+dp[f][j][0]);
                   }
                          sz[x]+=sz[f];
            }
            /// add point at x
            for(int i=sz[x];i>=0;--i)
                 dp[x][i+1][1]=min(dp[x][i+1][1],dp[x][i][0]),
                dp[x][i+1][0]=min(dp[x][i+1][0],dp[x][i][0]);

                sz[x]++;
  }
void solve()
{
  for(int i=1;i<n;i++)
     cin>>a[i].a>>a[i].b>>a[i].c>>a[i].d,
     v[a[i].a].pb(a[i].b),
     v[a[i].b].pb(a[i].a);
     dfs(1,0);
     for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        for(int f=0;f<2;f++)
        dp[i][j][f]=inf;
     for(int i=1;i<n;i++)
     {
         if(par[a[i].a]==a[i].b)
            swap(a[i].c,a[i].d),swap(a[i].a,a[i].b);
            c[a[i].b]={a[i].c,a[i].d};
     }
     dfs2(1,0);
    /// if(j==0) +.c
    /// if(j==end)+.d
    cin>>m;
    for(int i=1;i<=m;i++)
    {
         cin>>l;
          cout<<dp[1][l][1],down
    }
}
}
void phongbeo()
{
    cin>>n;
    if(n<=2000)sub4::solve();
    else
    {
        cout<<0;
        return;
    }
}

Compilation message (stderr)

designated_cities.cpp:74:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   74 | main()
      | ^~~~
designated_cities.cpp: In function 'void sub4::dfs2(long long int, long long int)':
designated_cities.cpp:106:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  106 |         for(auto f:v[x])
      |         ^~~
designated_cities.cpp:126:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  126 |             for(int i=sz[x];i>=0;--i)
      |             ^~~
designated_cities.cpp: In function 'void sub4::solve()':
designated_cities.cpp:134:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  134 |   for(int i=1;i<n;i++)
      |   ^~~
designated_cities.cpp:138:6: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  138 |      dfs(1,0);
      |      ^~~
designated_cities.cpp:145:10: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  145 |          if(par[a[i].a]==a[i].b)
      |          ^~
designated_cities.cpp:147:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  147 |             c[a[i].b]={a[i].c,a[i].d};
      |             ^
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
designated_cities.cpp:78:9: note: in expansion of macro 'fin'
   78 |         fin(task);
      |         ^~~
designated_cities.cpp:14:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define fou(x) freopen(x".ans","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:79:9: note: in expansion of macro 'fou'
   79 |         fou(task);
      |         ^~~

• Subtask 1: 6 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 17 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44