Submission #146165

#	Time	Username	Problem	Language	Result	Execution time	Memory
146165		evpipis	Tug of War (BOI15_tug)	C++11	100 / 100	2198 ms	6788 KiB

tug

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int, int> ii;

const int len = 6e4+4, zer = 3e5;
int vis[len], par[len], dep[len], cost[len], fron[len], lef[len], cnt;
vector<ii> adj[len], vec;
bitset<2*zer+1> bit;

int check(int u){
    vis[u] = 1;

    int ans = 2-adj[u].size();
    for (int j = 0; j < adj[u].size(); j++){
        ii v = adj[u][j];
        if (!vis[v.fi])
            ans += check(v.fi), fron[v.se] = 1;
    }

    return ans;
}

ii dfs(int u){
    vis[u] = ++cnt;

    ii ans = mp(0, 0);
    for (int j = 0; j < adj[u].size(); j++){
        ii v = adj[u][j];
        if (!vis[v.fi]){
            //printf("front edge: u = %d, v.se = %d\n", u, v.se);
            par[v.fi] = v.se;
            if (u&1)
                dep[v.fi] = dep[u]+cost[v.se], ans.fi += cost[v.se];
            else
                dep[v.fi] = dep[u]-cost[v.se], ans.fi -= cost[v.se];

            ii cur = dfs(v.fi);
            ans.fi += cur.fi;
            ans.se += cur.se;
        }
        else if (vis[v.fi] < vis[u] && par[u] != v.se){
            //printf("back edge: u = %d, v.se = %d\n", u, v.se);
            int ed = -cost[v.se];
            if (u&1)
                ed = cost[v.se];

            ans.se += dep[u]-dep[v.fi]+ed;
            ans.fi += ed-ans.se;
        }
    }

    //printf("u = %d, dep = %d, ans = (%d, %d)\n", u, dep[u], ans.fi, ans.se);
    return ans;
}

int main(){
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= 2*n; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        cost[i] = c;
        lef[i] = 2*a-2;
        adj[2*a-2].pb(mp(2*b-1, i));
        adj[2*b-1].pb(mp(2*a-2, i));
    }

    for (int i = 1; i <= n; i++)
        if (!vis[2*i-2] && check(2*i-2) != 0){
            printf("NO\n");
            return 0;
        }

    for (int i = 0; i < 2*n; i++)
        vis[i] = 0;

    for (int i = 1; i <= 2*n; i++)
        if (!fron[i] && !vis[lef[i]])
            vec.pb(dfs(lef[i]));
    for (int i = 0; i < vec.size(); i++)
        vec[i].se = abs(vec[i].se);

    //for (int i = 0; i < vec.size(); i++)
      //  printf("(%d, %d)\n", vec[i].fi, vec[i].se);

    //vec.clear();
    //for (int i = 0; i < 100; i++)
      //  vec.pb(mp(0, 0));

    bit[zer] = 1;
    for (int i = 0; i < vec.size(); i++){
        if (vec[i].fi > 0)
            bit >>= (vec[i].fi);
        else if (vec[i].fi < 0)
            bit <<= (-vec[i].fi);

        if (vec[i].se)
            bit = (bit>>vec[i].se)|(bit<<vec[i].se);
    }

    for (int i = max(0, zer-k); i <= min(2*zer, zer+k); i++)
        if (bit[i]){
            printf("YES\n");
            return 0;
        }

    printf("NO\n");
    return 0;
}
/*
4 0
1 1 1
2 1 1
3 1 1
3 2 1
3 3 1
1 3 1
4 3 1
4 4 1
*/

Compilation message (stderr)

tug.cpp: In function 'int check(int)':
tug.cpp:19:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
tug.cpp: In function 'ii dfs(int)':
tug.cpp:32:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
tug.cpp: In function 'int main()':
tug.cpp:85:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++)
                     ~~^~~~~~~~~~~~
tug.cpp:96:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++){
                     ~~^~~~~~~~~~~~
tug.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~
tug.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 23 / 23
• Subtask 4: 29 / 29