oj.uz

Submission #1079926

# Submission time Handle Problem Language Result Execution time Memory
1079926 2024-08-29T03:33:48 Z LIF Stranded Far From Home (BOI22_island) C++14
10 / 100
 383 ms 63936 KB 
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt = 0;
long long int a[500005],head[500005];
int x[500005];
int y[500005];
vector<long long int> val;
map<int,vector<int> > mp;
int f[500005];
vector<int> vv[500005];
long long int siz[500005];
int tag[500005];
int find(int x)
{
    if(f[x] == x)return x;
    return f[x] = find(f[x]);
}
struct e
{
    int to;
    int next;
}edge[500005];
void add(int x,int y)
{
    cnt++;
    edge[cnt].to = y;
    edge[cnt].next = head[x];
    head[x] = cnt;
}
void dfs(int now,int fa,int tg)
{
    tag[now] = tg;
    for(int i=head[now];i!=0;i=edge[i].next)
    {
        int to = edge[i].to;
        if(to == fa)continue;
        if(tag[to] == -1 || tg == -1)dfs(to,now,-1);
        else dfs(to,now,1);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(mp[a[i]].size() == 0)val.push_back(a[i]);
        mp[a[i]].push_back(i);
        tag[i] = 1;
    }
    for(int i=1;i<=n;i++)siz[i] = a[i];
    for(int i=1;i<=n;i++)f[i] = i;
    for(int i=1;i<=m;i++)
    {
        cin>>x[i]>>y[i];
        vv[x[i]].push_back(y[i]);vv[y[i]].push_back(x[i]);
    }
    sort(val.begin(),val.end());
    val.push_back(-1);
    for(int i=0;i<val.size()-1;i++)
    {
        for(auto nowid : mp[val[i]])
        {
            for(auto toid : vv[nowid])
            {
                if(a[toid] <= a[nowid])
                {
                    if(find(toid) == find(nowid))continue;

                        if(val[i] > siz[find(toid)])
                        {
                            tag[find(toid)] = -1;
                            // cout<<"fail"<<endl;
                            // cout<<val[i]<<" "<<toid<<" "<<siz[toid]<<endl;
                        }
                        siz[find(nowid)] += siz[find(toid)];
                
                        f[find(toid)] = find(nowid);
                        add(nowid,toid);
                        // cout<<"yeah"<<endl;
                        // cout<<nowid<<" "<<toid<<endl;
                }
            }
            
        }
    }
    // for(int i=1;i<=n;i++)cout<<tag[i];
    // cout<<endl;
    int fir = find(1);
    dfs(fir,0,1);
    for(int i=1;i<=n;i++)
    {
        if(tag[i] == -1)cout<<"0";
        else cout<<"1";
    }
    cout<<endl;

    









    return 0;
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i=0;i<val.size()-1;i++)
      |                 ~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12120 KB Output is correct
2 Correct 5 ms 12124 KB Output is correct
3 Correct 6 ms 12144 KB Output is correct
4 Incorrect 9 ms 12380 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12120 KB Output is correct
2 Correct 5 ms 12124 KB Output is correct
3 Correct 299 ms 56408 KB Output is correct
4 Correct 177 ms 33620 KB Output is correct
5 Correct 269 ms 50368 KB Output is correct
6 Correct 249 ms 45988 KB Output is correct
7 Correct 320 ms 51644 KB Output is correct
8 Correct 193 ms 28868 KB Output is correct
9 Correct 236 ms 45080 KB Output is correct
10 Correct 201 ms 45128 KB Output is correct
11 Correct 143 ms 28048 KB Output is correct
12 Correct 157 ms 28868 KB Output is correct
13 Correct 183 ms 41152 KB Output is correct
14 Correct 162 ms 41412 KB Output is correct
15 Correct 276 ms 63936 KB Output is correct
16 Correct 226 ms 63420 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12124 KB Output is correct
2 Incorrect 383 ms 51088 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12120 KB Output is correct
2 Incorrect 197 ms 28876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12120 KB Output is correct
2 Correct 5 ms 12124 KB Output is correct
3 Correct 6 ms 12144 KB Output is correct
4 Incorrect 9 ms 12380 KB Output isn't correct
5 Halted 0 ms 0 KB -