oj.uz

Submission #1079897

# Submission time Handle Problem Language Result Execution time Memory
1079897 2024-08-29T03:16:38 Z LIF Stranded Far From Home (BOI22_island) C++14
10 / 100
 380 ms 67624 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(used[find(toid)] == false)
                    {
                        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)];
                        used[find(toid)] = true;
                        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 6 ms 12124 KB Output is correct
2 Correct 5 ms 12124 KB Output is correct
3 Correct 5 ms 12204 KB Output is correct
4 Incorrect 8 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 12124 KB Output is correct
2 Correct 6 ms 12204 KB Output is correct
3 Correct 281 ms 60060 KB Output is correct
4 Correct 150 ms 36804 KB Output is correct
5 Correct 281 ms 53652 KB Output is correct
6 Correct 257 ms 49604 KB Output is correct
7 Correct 280 ms 55252 KB Output is correct
8 Correct 192 ms 33216 KB Output is correct
9 Correct 234 ms 48840 KB Output is correct
10 Correct 300 ms 57632 KB Output is correct
11 Correct 233 ms 40856 KB Output is correct
12 Correct 165 ms 31936 KB Output is correct
13 Correct 153 ms 44232 KB Output is correct
14 Correct 159 ms 44232 KB Output is correct
15 Correct 268 ms 67624 KB Output is correct
16 Correct 229 ms 66504 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12120 KB Output is correct
2 Incorrect 216 ms 33576 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 12124 KB Output is correct
2 Correct 5 ms 12124 KB Output is correct
3 Correct 5 ms 12204 KB Output is correct
4 Incorrect 8 ms 12380 KB Output isn't correct
5 Halted 0 ms 0 KB -