oj.uz

Submission #1021949

# Submission time Handle Problem Language Result Execution time Memory
1021949 2024-07-13T08:06:16 Z yeediot Tug of War (BOI15_tug) C++17
23 / 100
 1249 ms 8656 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void CHECK();
void setio(){
    freopen("/Users/iantsai/cpp/input.txt","r",stdin);
    freopen("/Users/iantsai/cpp/output.txt","w",stdout);
}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
#define TOI_is_so_de ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);setio();
const int mxn = 30005;
int n, k, lv[mxn * 4], low[mxn * 4], scc[mxn * 4], cnt, timer;
vector<int>adj[mxn * 4], l[mxn], r[mxn], st;
void tarjan(int v){
    low[v] = lv[v] = ++timer;
    st.pb(v);
    for(auto u : adj[v]){
        if(!lv[u]){
            tarjan(u);
            chmin(low[v], low[u]);
        }
        else if(!scc[u]){
            chmin(low[v], lv[u]);
        }
    }
    if(low[v] == lv[v]){
        cnt++;
        int k;
        do{
            k = st.back();
            st.pop_back();
            scc[k] = cnt;
        }while(k != v);
    }
}
void solve(){
    cin >> n >> k;
    vector<array<int, 3>>vec, temp;
    vec.pb({-1000000000, 0 , 0});
    for(int i = 1; i <= 2 * n; i++){
        int L, R, s;
        cin >> L >> R >> s;
        vec.pb({s, L, R});
    }
    bitset<mxn * 40>bs;
    bs[mxn * 20] = 1;
    for(int i = 1; i <= 2 * n; i++){
        bs = (bs << vec[i][0]) | (bs >> vec[i][0]);
    }
    for(int i = 1; i <= 2 * n; i++){
        auto [s, L, R] = vec[i];
        l[L].pb(i);
        r[R].pb(i);
    }
    for(int i = 1; i <= n; i++){
        if(sz(l[i]) == 0 or sz(r[i]) == 0){
            debug("YEE");
            cout << "NO\n";
            return;
        }
    }
    for(int i = 1; i <= n; i++){
        for(auto x : l[i]){
            for(auto y : l[i]){
                if(x == y) continue;
                adj[x].pb(y + 2 * n);
            }
        }
        for(auto x : r[i]){
            for(auto y : r[i]){
                if(x == y) continue;
                adj[x + 2 * n].pb(y);
            }
        }
    }
    for(int i = 1; i <= 4 * n; i++){
        if(!lv[i]) tarjan(i);
    }
    int dif = 0;
    for(int i = 1; i <= 2 * n; i++){
        debug(scc[i], scc[i + 2 * n]);
        if(scc[i] == scc[i + 2 * n]){
            debug("YEE2");
            cout << "NO\n";
            return;
        }
        else if(scc[i] < scc[i + 2 * n]){
        }
    }
    bool ok = 0;
    for(int i = mxn * 20 - k; i <= mxn * 20 + k; i++){
        ok |= bs[i];
    }
    cout << (ok ? "YES\n" : "NO\n");
}
signed main(){
    TOI_is_so_de;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    #ifdef local
    CHECK();
    #endif
}
/*
input:
 
*/
#ifdef local
void CHECK(){
    cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    function<bool(string,string)> compareFiles = [](string p1, string p2)->bool {
        std::ifstream file1(p1);
        std::ifstream file2(p2);
        if(!file1.is_open() || !file2.is_open()) return false;
        std::string line1, line2;
        while (getline(file1, line1) && getline(file2, line2)) {
            if (line1 != line2)return false;
        }
        int cnta = 0, cntb = 0;
        while(getline(file1,line1))cnta++;
        while(getline(file2,line2))cntb++;
        return cntb - cnta <= 1;
    };
    bool check = compareFiles("output.txt","expected.txt");
    if(check) cerr<<"ACCEPTED\n";
    else cerr<<"WRONG ANSWER!\n";
}
#else
#endif

Compilation message

tug.cpp: In function 'void solve()':
tug.cpp:114:9: warning: unused variable 'dif' [-Wunused-variable]
  114 |     int dif = 0;
      |         ^~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5208 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 4 ms 5212 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 3 ms 5128 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 5268 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 4 ms 5208 KB Output is correct
13 Correct 3 ms 5208 KB Output is correct
14 Correct 4 ms 5212 KB Output is correct
15 Correct 4 ms 5212 KB Output is correct
16 Correct 3 ms 5212 KB Output is correct
17 Correct 5 ms 5268 KB Output is correct
18 Correct 4 ms 5212 KB Output is correct
19 Correct 4 ms 5268 KB Output is correct
20 Correct 3 ms 5208 KB Output is correct
21 Correct 3 ms 5212 KB Output is correct
22 Correct 4 ms 5212 KB Output is correct
23 Incorrect 3 ms 5212 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5208 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 4 ms 5212 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 3 ms 5128 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 5268 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 4 ms 5208 KB Output is correct
13 Correct 3 ms 5208 KB Output is correct
14 Correct 4 ms 5212 KB Output is correct
15 Correct 4 ms 5212 KB Output is correct
16 Correct 3 ms 5212 KB Output is correct
17 Correct 5 ms 5268 KB Output is correct
18 Correct 4 ms 5212 KB Output is correct
19 Correct 4 ms 5268 KB Output is correct
20 Correct 3 ms 5208 KB Output is correct
21 Correct 3 ms 5212 KB Output is correct
22 Correct 4 ms 5212 KB Output is correct
23 Incorrect 3 ms 5212 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1139 ms 8648 KB Output is correct
2 Correct 1150 ms 6592 KB Output is correct
3 Correct 1105 ms 8632 KB Output is correct
4 Correct 1210 ms 6596 KB Output is correct
5 Correct 1117 ms 8648 KB Output is correct
6 Correct 1087 ms 6592 KB Output is correct
7 Correct 1123 ms 8632 KB Output is correct
8 Correct 1124 ms 6604 KB Output is correct
9 Correct 1102 ms 8644 KB Output is correct
10 Correct 1171 ms 6596 KB Output is correct
11 Correct 1102 ms 8644 KB Output is correct
12 Correct 1089 ms 6596 KB Output is correct
13 Correct 1118 ms 8644 KB Output is correct
14 Correct 1096 ms 8656 KB Output is correct
15 Correct 1167 ms 6588 KB Output is correct
16 Correct 1205 ms 8640 KB Output is correct
17 Correct 1155 ms 6600 KB Output is correct
18 Correct 1249 ms 8652 KB Output is correct
19 Correct 1083 ms 6592 KB Output is correct
20 Correct 1150 ms 8648 KB Output is correct
21 Correct 1195 ms 6608 KB Output is correct
22 Correct 1191 ms 8656 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5208 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 4 ms 5212 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 3 ms 5128 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 5268 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 4 ms 5208 KB Output is correct
13 Correct 3 ms 5208 KB Output is correct
14 Correct 4 ms 5212 KB Output is correct
15 Correct 4 ms 5212 KB Output is correct
16 Correct 3 ms 5212 KB Output is correct
17 Correct 5 ms 5268 KB Output is correct
18 Correct 4 ms 5212 KB Output is correct
19 Correct 4 ms 5268 KB Output is correct
20 Correct 3 ms 5208 KB Output is correct
21 Correct 3 ms 5212 KB Output is correct
22 Correct 4 ms 5212 KB Output is correct
23 Incorrect 3 ms 5212 KB Output isn't correct
24 Halted 0 ms 0 KB -