oj.uz

답안 #573277

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
573277 2022-06-06T10:42:19 Z MohamedAliSaidane Stranded Far From Home (BOI22_island) C++14
10 / 100
 312 ms 12800 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];

        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 ;
            }
        }

        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';

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 195 ms 5076 KB Output is correct
5 Correct 199 ms 5100 KB Output is correct
6 Correct 276 ms 5100 KB Output is correct
7 Correct 185 ms 5076 KB Output is correct
8 Correct 138 ms 5104 KB Output is correct
9 Correct 312 ms 5156 KB Output is correct
10 Correct 99 ms 5076 KB Output is correct
11 Correct 96 ms 5092 KB Output is correct
12 Correct 114 ms 5096 KB Output is correct
13 Correct 181 ms 5196 KB Output is correct
14 Correct 109 ms 5104 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Incorrect 96 ms 12800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 95 ms 12716 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 105 ms 12756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 195 ms 5076 KB Output is correct
5 Correct 199 ms 5100 KB Output is correct
6 Correct 276 ms 5100 KB Output is correct
7 Correct 185 ms 5076 KB Output is correct
8 Correct 138 ms 5104 KB Output is correct
9 Correct 312 ms 5156 KB Output is correct
10 Correct 99 ms 5076 KB Output is correct
11 Correct 96 ms 5092 KB Output is correct
12 Correct 114 ms 5096 KB Output is correct
13 Correct 181 ms 5196 KB Output is correct
14 Correct 109 ms 5104 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Incorrect 96 ms 12800 KB Output isn't correct
18 Halted 0 ms 0 KB -