Submission #79787

#	Time	Username	Problem	Language	Result	Execution time	Memory
79787		Vinhspm	Tug of War (BOI15_tug)	C++14	0 / 100	52 ms	28884 KiB

tug

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
typedef pair<int, int> ii;

const int N = 1e5;
const int M = 20 * 30000;
const int oo = 1e9;

ii a[N];
int n, maxn, sum, suma, cnt, curval, total;
int cost[N], deg[N], f[350][20 * 30005];
bool alive[N], visit[N];
vector<int> vi[N];
map<int, int> val;

void bad()  { cout << "NO"; exit(0); }
void upd(int &x, int y) { x = min(x, y); }
void addeg(int u, int v) {
    deg[u] ++; deg[v] ++;
    vi[u].pb(v); vi[v].pb(u);
}

void kill(int u)    {
    int u1 = 0, tmp = 0;
    for(int v: vi[u]) if(!alive[v]) {
        u1 = v; tmp ++;
    }
    if(tmp > 1) return;
    if(u <= 3*n) curval += cost[u1];
    alive[u] = alive[u1] = 1;
    for(int v: vi[u1]) if(!alive[v])
        kill(v); // :D
}

void check(int u)   {
    visit[u] = true;
    int nex = -1;
    for(int v: vi[u]) if(!visit[v]) {
        nex = v; break;
    }
    if(nex == -1) bad(); visit[nex] = true;
    for(int v: vi[nex]) if(!visit[v])
        check(v);
    return; // :D
}

void dfs(int u, bool spm)   {
    if(spm == 0) suma += cost[u];
    sum += cost[u];
    alive[u] = true;
    int nex = -1;
    for(int v: vi[u]) if(!alive[v]) {
        nex = v; break;
    }
    alive[nex] = true;
    for(int v: vi[nex]) if(!alive[v])
        dfs(v, 1 - spm);
}

signed main() {
    //freopen("test.inp", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	scanf("%d%d", &n, &maxn);
    for(int i = 1; i <= 2*n; ++i) {
        int l, r, c; scanf("%d%d%d", &l, &r, &c);
        total += c;
        addeg(i, 2*n + l);
        addeg(3*n + r, i);
        cost[i] = c;
    }

    for(int i = 1; i <= 2*n; ++i) if(!visit[i])
        check(i);
    for(int i = 2*n + 1; i <= 4*n; ++i) if(deg[i] == 1)
        kill(i);
    // now we have all the circle
    for(int i = 1; i <= 2*n; ++i) if(!alive[i]) {
        sum = suma = 0;
        dfs(i, 0);
        curval += min(suma, sum - suma);
        int x = max(suma, sum - suma) - min(suma, sum - suma);
        val[x] ++;
    }
    for(auto it = val.begin(); it != val.end(); ++it)
        a[++cnt] = ii(it->fi, it->se); // :D
    a[0].se = 0;
    //for(int i = 1; i <= n; ++i) cout << a[i].fi << ' ' << a[i].se << '\n';
    //cout << curval << ' ' << total << '\n';
    for(int i = 0; i <= cnt; ++i) for(int j = 0; j <= M; ++j) f[i][j] = oo;
    f[0][0] = 0;
    for(int i = 0; i <= cnt; ++i) for(int j = 0; j <= M; ++j) if(f[i][j] <= a[i].se)    {
        if(f[i][j] < a[i].se) upd(f[i][j + a[i].fi], f[i][j] + 1);
        upd(f[i + 1][j], 0);
    }
    for(int i = 0; i <= M; ++i) if(f[cnt][i] <= a[cnt].se) {
        if(abs(2*(curval + i) - total) <= maxn)
            return cout << "YES", 0;
    }
     return cout << "NO", 0;
}

Compilation message (stderr)

tug.cpp: In function 'void check(int)':
tug.cpp:44:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(nex == -1) bad(); visit[nex] = true;
     ^~
tug.cpp:44:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     if(nex == -1) bad(); visit[nex] = true;
                          ^~~~~
tug.cpp: In function 'int main()':
tug.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &maxn);
  ~~~~~^~~~~~~~~~~~~~~~~~~
tug.cpp:69:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int l, r, c; scanf("%d%d%d", &l, &r, &c);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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