oj.uz

Submission #1079918

# Submission time Handle Problem Language Result Execution time Memory
1079918 2024-08-29T03:29:52 Z LIF Stranded Far From Home (BOI22_island) C++14
10 / 100
 375 ms 70396 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<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]])
        {
            map<int,bool> used;
            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<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 5 ms 15452 KB Output is correct
2 Correct 5 ms 15452 KB Output is correct
3 Correct 4 ms 15452 KB Output is correct
4 Incorrect 9 ms 15916 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 15452 KB Output is correct
2 Correct 5 ms 15452 KB Output is correct
3 Correct 256 ms 62804 KB Output is correct
4 Correct 185 ms 39412 KB Output is correct
5 Correct 286 ms 56516 KB Output is correct
6 Correct 228 ms 52420 KB Output is correct
7 Correct 307 ms 57748 KB Output is correct
8 Correct 192 ms 36036 KB Output is correct
9 Correct 250 ms 51468 KB Output is correct
10 Correct 190 ms 50880 KB Output is correct
11 Correct 134 ms 33988 KB Output is correct
12 Correct 157 ms 34504 KB Output is correct
13 Correct 142 ms 46784 KB Output is correct
14 Correct 151 ms 47048 KB Output is correct
15 Correct 311 ms 70396 KB Output is correct
16 Correct 237 ms 69056 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15448 KB Output is correct
2 Incorrect 375 ms 57540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15448 KB Output is correct
2 Incorrect 184 ms 35944 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15452 KB Output is correct
2 Correct 5 ms 15452 KB Output is correct
3 Correct 4 ms 15452 KB Output is correct
4 Incorrect 9 ms 15916 KB Output isn't correct
5 Halted 0 ms 0 KB -