oj.uz

Submission #580176

# Submission time Handle Problem Language Result Execution time Memory
580176 2022-06-20T16:55:09 Z wdjpng Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 38360 KB 
#include <bits/stdc++.h>

#define int long long
#define double long double
#define rep(i,n) for(int i =0; i<n; i++)
#define all(a) a.begin(),a.end()

using namespace std;

int n,m;
vector<int>s;
vector<vector<int>>E;
vector<int>chef(2e5+1);

struct uni
{
    int sum=0;
    set<int>bord;
};

vector<uni>unis(2e5+1);

int find(int a)
{
    if(a==chef[a]) return a;
    return chef[a]=find(chef[a]);
}

void unite(int a, int b) {
    a=find(a);
    b=find(b);
    if(unis[b].bord.size()>unis[a].bord.size()) swap(a,b);
    for(int i : unis[b].bord) if(!unis[a].bord.count(i)) {unis[a].sum+=s[i]; unis[a].bord.insert(i);}
}

bool sorti(int a, int b)
{
    return s[a]<s[b];
}
signed main()
{
    cin>>n>>m;
    if(n==1) {cout<<"1\n"; exit(0);}
    s.resize(n);
    rep(i,n) cin>>s[i];

    E.resize(n);
    rep(i,m)
    {
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    rep(i,n)
    {
        chef[i]=i;
        unis[i].bord.insert(i);
        unis[i].sum=s[i];
    }

    vector<int>ord(n);
    rep(i,n) ord[i]=i;

    int totsum=0;
    rep(i,n) totsum+=s[i];

    sort(all(ord), sorti);
    vector<bool>sol(n,false);
    rep(v,n)
    {
        int sum = s[v];
        vector<bool>vis(n,false);
        vis[v]=true;

        bool ischange=true, halt=false;
        priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>>pq;
        for(int w : E[v]) if(!vis[w]) {pq.push({s[w],w}); vis[w]=true;}
        while (pq.size()&&pq.top().first<=sum&&!halt)
        {
            auto blub=pq.top();
            pq.pop();

            sum+=blub.first;
            for(int w : E[blub.second]) if(!vis[w]) {pq.push({s[w],w}); vis[w]=true;}
            halt|=sum==totsum||sol[blub.second];
        }
        sol[v]=halt;
    }

    rep(i,n) cout<<(sol[i]?'1':'0');
    cout<<'\n';
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:79:14: warning: unused variable 'ischange' [-Wunused-variable]
   79 |         bool ischange=true, halt=false;
      |              ^~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 8 ms 12756 KB Output is correct
3 Correct 7 ms 12708 KB Output is correct
4 Correct 14 ms 13012 KB Output is correct
5 Correct 11 ms 13012 KB Output is correct
6 Correct 10 ms 13012 KB Output is correct
7 Correct 11 ms 12972 KB Output is correct
8 Correct 10 ms 13020 KB Output is correct
9 Correct 230 ms 13104 KB Output is correct
10 Correct 10 ms 13012 KB Output is correct
11 Correct 10 ms 13040 KB Output is correct
12 Correct 10 ms 13064 KB Output is correct
13 Correct 144 ms 13052 KB Output is correct
14 Correct 98 ms 13012 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12756 KB Output is correct
2 Correct 6 ms 12756 KB Output is correct
3 Execution timed out 1089 ms 38360 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12756 KB Output is correct
2 Correct 559 ms 36416 KB Output is correct
3 Correct 597 ms 36476 KB Output is correct
4 Correct 443 ms 36480 KB Output is correct
5 Execution timed out 1097 ms 36240 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 980 ms 37580 KB Output is correct
3 Execution timed out 1042 ms 37464 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 8 ms 12756 KB Output is correct
3 Correct 7 ms 12708 KB Output is correct
4 Correct 14 ms 13012 KB Output is correct
5 Correct 11 ms 13012 KB Output is correct
6 Correct 10 ms 13012 KB Output is correct
7 Correct 11 ms 12972 KB Output is correct
8 Correct 10 ms 13020 KB Output is correct
9 Correct 230 ms 13104 KB Output is correct
10 Correct 10 ms 13012 KB Output is correct
11 Correct 10 ms 13040 KB Output is correct
12 Correct 10 ms 13064 KB Output is correct
13 Correct 144 ms 13052 KB Output is correct
14 Correct 98 ms 13012 KB Output is correct
15 Correct 8 ms 12756 KB Output is correct
16 Correct 6 ms 12756 KB Output is correct
17 Execution timed out 1089 ms 38360 KB Time limit exceeded
18 Halted 0 ms 0 KB -