oj.uz

Submission #573290

# Submission time Handle Problem Language Result Execution time Memory
573290 2022-06-06T11:17:56 Z MohamedAliSaidane Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 16252 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

        using namespace __gnu_pbds;
        using namespace std;

        typedef tree<int,null_type,less<int>,rb_tree_tag,
        tree_order_statistics_node_update> indexed_set;

        typedef long long ll;
        typedef long double ld;

        typedef pair<int,int> pii;
        typedef pair<ll,ll> pll;
        typedef pair<ld,ld> pld;

        typedef vector<int> vi;
        typedef vector<ll> vll;
        typedef vector<pii> vpi;
        typedef vector<pll> vpl;

        #define pb push_back
        #define popb pop_back
        #define pp pop_back
        #define pf push_front
        #define popf pop_front
        #define all(x) (x).begin(),(x).end()
        #define ff first
        #define ss second

        ///#define int ll

        int nx[4] = {0,0,1,-1}, ny[4] = {1,-1,0,0};
        ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
        ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}

        const int nax = 2e5 + 4;
        int n, m;
        ll s[nax];
        vi adj[nax];
        ll pref[nax];
        void sub1()
        {
            string ans = "";
            for(int i = 1; i<= n; i++)
                ans += '1';
            ll sum = 0ll;
            for(int i  = 1 ; i <= n ;i ++ )
                sum += s[i];
            for(int i = 1; i <= n; i++)
            {
                ll cur = s[i];
                set<pll> pq;
                for(auto e: adj[i])
                    pq.insert({s[e],e});
                bool vis[n + 1];
                memset(vis,false,sizeof(vis));
                vis[i] = 1;
                while(!pq.empty())
                {
                    pll u = *(pq.begin());
                    pq.erase(pq.begin());
                    if(u.ff > cur)
                    {
                        ans[i - 1] = '0';
                        vis[u.ss] = 0;
                        break;
                    }
                    cur += u.ff;
                    vis[u.ss] = 1;
                    for(auto e: adj[u.ss])
                    {
                        if(vis[e])
                            continue;
                        vis[e]  = 1;
                        pq.insert({s[e],e});
                    }
                }
                if(cur < sum)
                    ans[ i - 1] - '0';
            }
            cout << ans;
        }
        void solve()
        {
            cin >> n >> m;
            for(int i = 1; i <= n; i++)
                cin >> s[i];
            for(int i = 1; i <= m; i ++)
            {
                int a, b;
                cin >> a >> b;
                adj[a].pb(b);
                adj[b].pb(a);
            }
            if(n <= 2000 && m <= 2000)
            {
                sub1();
                return ;
            }

            for(int i = 1;i  <= n ;i++)
                pref[i] = pref[i - 1] + s[i];
            int mint[n + 1];
            int maxt[n + 1];
            string ans = "";
            for(int i = 1; i <= n; i++)
            {
                mint[i] = maxt[i] = i;
                ans += '1';
            }

            for(int node = 1; node <= n; node++)
            {
                ll cur = s[node];
                int i = node - 1, j= node + 1;
                //cout << node << endl;
                while(i > 0 || j <= n)
                {
                    cur = pref[j] - pref[i];
                    j = maxt[i + 1] + 1;
                    //cout << node << ' ' << i << ' ' << j << endl;
                    if(i >= 1)
                    {
                        //cout << i << endl;
                        if(s[i] <= cur)
                        {
                            maxt[i] = j - 1;
                            mint[j - 1] = i;

                            i --;
                            continue;
                        }
                    }
                    if(j <= n)
                    {
                        //cout << j << endl;
                        if(s[j] <= cur)
                        {
                            maxt[i + 1] = j;
                            mint[j] = i + 1;
                            j ++;
                            continue;
                        }
                    }
                    break;
                }
                //cout << node << ' ' << i << ' ' << j << endl;
                ans[node - 1] = (char)((int)('0') + (i == 0 && j == n + 1));
            }
            cout << ans;
        }

        int32_t main()
        {
            ios::sync_with_stdio(false);
            cin.tie(0); cout.tie(0);
            int tt = 1;
            while(tt --)
                solve();
        }

Compilation message

island.cpp: In function 'void sub1()':
island.cpp:80:33: warning: value computed is not used [-Wunused-value]
   80 |                     ans[ i - 1] - '0';
island.cpp: In function 'void solve()':
island.cpp:104:17: warning: variable 'mint' set but not used [-Wunused-but-set-variable]
  104 |             int mint[n + 1];
      |                 ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 199 ms 5108 KB Output is correct
5 Correct 214 ms 5104 KB Output is correct
6 Correct 293 ms 5108 KB Output is correct
7 Correct 188 ms 5108 KB Output is correct
8 Correct 147 ms 5092 KB Output is correct
9 Correct 315 ms 5172 KB Output is correct
10 Correct 94 ms 5076 KB Output is correct
11 Correct 89 ms 5076 KB Output is correct
12 Correct 138 ms 5076 KB Output is correct
13 Correct 178 ms 5092 KB Output is correct
14 Correct 110 ms 5096 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Execution timed out 1072 ms 16236 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 1087 ms 16172 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 1075 ms 16252 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 199 ms 5108 KB Output is correct
5 Correct 214 ms 5104 KB Output is correct
6 Correct 293 ms 5108 KB Output is correct
7 Correct 188 ms 5108 KB Output is correct
8 Correct 147 ms 5092 KB Output is correct
9 Correct 315 ms 5172 KB Output is correct
10 Correct 94 ms 5076 KB Output is correct
11 Correct 89 ms 5076 KB Output is correct
12 Correct 138 ms 5076 KB Output is correct
13 Correct 178 ms 5092 KB Output is correct
14 Correct 110 ms 5096 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4952 KB Output is correct
17 Execution timed out 1072 ms 16236 KB Time limit exceeded
18 Halted 0 ms 0 KB -