oj.uz

Submission #1079941

# Submission time Handle Problem Language Result Execution time Memory
1079941 2024-08-29T04:02:40 Z LIF Stranded Far From Home (BOI22_island) C++14
100 / 100
 363 ms 77760 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());
    for(int i=0;i<val.size();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)];
                        add(find(nowid),find(toid));
                        f[find(toid)] = find(nowid);
                        //cout<<"yeah"<<endl;
                        //cout<<find(nowid)<<" "<<find(toid)<<endl;
                        //cout<<"set: "<<endl;
                        //for(int j=1;j<=n;j++)cout<<find(j)<<" "<<siz[find(j)]<<endl;
                        //cout<<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:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=0;i<val.size();i++)
      |                 ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24924 KB Output is correct
2 Correct 3 ms 25064 KB Output is correct
3 Correct 3 ms 22872 KB Output is correct
4 Correct 6 ms 25180 KB Output is correct
5 Correct 5 ms 25180 KB Output is correct
6 Correct 4 ms 25180 KB Output is correct
7 Correct 5 ms 25328 KB Output is correct
8 Correct 5 ms 25180 KB Output is correct
9 Correct 4 ms 25068 KB Output is correct
10 Correct 6 ms 25320 KB Output is correct
11 Correct 5 ms 25436 KB Output is correct
12 Correct 5 ms 25180 KB Output is correct
13 Correct 4 ms 25180 KB Output is correct
14 Correct 7 ms 25176 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24924 KB Output is correct
2 Correct 3 ms 23000 KB Output is correct
3 Correct 250 ms 70076 KB Output is correct
4 Correct 131 ms 39636 KB Output is correct
5 Correct 263 ms 64036 KB Output is correct
6 Correct 218 ms 59584 KB Output is correct
7 Correct 255 ms 65216 KB Output is correct
8 Correct 157 ms 40904 KB Output is correct
9 Correct 193 ms 58812 KB Output is correct
10 Correct 184 ms 57960 KB Output is correct
11 Correct 128 ms 40648 KB Output is correct
12 Correct 143 ms 40900 KB Output is correct
13 Correct 121 ms 39496 KB Output is correct
14 Correct 120 ms 39620 KB Output is correct
15 Correct 266 ms 77756 KB Output is correct
16 Correct 227 ms 76480 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22876 KB Output is correct
2 Correct 352 ms 65100 KB Output is correct
3 Correct 312 ms 59596 KB Output is correct
4 Correct 150 ms 40984 KB Output is correct
5 Correct 131 ms 39304 KB Output is correct
6 Correct 342 ms 65108 KB Output is correct
7 Correct 281 ms 77716 KB Output is correct
8 Correct 276 ms 77760 KB Output is correct
9 Correct 233 ms 76620 KB Output is correct
10 Correct 214 ms 59332 KB Output is correct
11 Correct 177 ms 43840 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 198 ms 43328 KB Output is correct
3 Correct 191 ms 42836 KB Output is correct
4 Correct 190 ms 42832 KB Output is correct
5 Correct 186 ms 42700 KB Output is correct
6 Correct 164 ms 42696 KB Output is correct
7 Correct 163 ms 47816 KB Output is correct
8 Correct 142 ms 46672 KB Output is correct
9 Correct 115 ms 37712 KB Output is correct
10 Correct 143 ms 40888 KB Output is correct
11 Correct 133 ms 42940 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24924 KB Output is correct
2 Correct 3 ms 25064 KB Output is correct
3 Correct 3 ms 22872 KB Output is correct
4 Correct 6 ms 25180 KB Output is correct
5 Correct 5 ms 25180 KB Output is correct
6 Correct 4 ms 25180 KB Output is correct
7 Correct 5 ms 25328 KB Output is correct
8 Correct 5 ms 25180 KB Output is correct
9 Correct 4 ms 25068 KB Output is correct
10 Correct 6 ms 25320 KB Output is correct
11 Correct 5 ms 25436 KB Output is correct
12 Correct 5 ms 25180 KB Output is correct
13 Correct 4 ms 25180 KB Output is correct
14 Correct 7 ms 25176 KB Output is correct
15 Correct 3 ms 24924 KB Output is correct
16 Correct 3 ms 23000 KB Output is correct
17 Correct 250 ms 70076 KB Output is correct
18 Correct 131 ms 39636 KB Output is correct
19 Correct 263 ms 64036 KB Output is correct
20 Correct 218 ms 59584 KB Output is correct
21 Correct 255 ms 65216 KB Output is correct
22 Correct 157 ms 40904 KB Output is correct
23 Correct 193 ms 58812 KB Output is correct
24 Correct 184 ms 57960 KB Output is correct
25 Correct 128 ms 40648 KB Output is correct
26 Correct 143 ms 40900 KB Output is correct
27 Correct 121 ms 39496 KB Output is correct
28 Correct 120 ms 39620 KB Output is correct
29 Correct 266 ms 77756 KB Output is correct
30 Correct 227 ms 76480 KB Output is correct
31 Correct 3 ms 22876 KB Output is correct
32 Correct 352 ms 65100 KB Output is correct
33 Correct 312 ms 59596 KB Output is correct
34 Correct 150 ms 40984 KB Output is correct
35 Correct 131 ms 39304 KB Output is correct
36 Correct 342 ms 65108 KB Output is correct
37 Correct 281 ms 77716 KB Output is correct
38 Correct 276 ms 77760 KB Output is correct
39 Correct 233 ms 76620 KB Output is correct
40 Correct 214 ms 59332 KB Output is correct
41 Correct 177 ms 43840 KB Output is correct
42 Correct 4 ms 22876 KB Output is correct
43 Correct 198 ms 43328 KB Output is correct
44 Correct 191 ms 42836 KB Output is correct
45 Correct 190 ms 42832 KB Output is correct
46 Correct 186 ms 42700 KB Output is correct
47 Correct 164 ms 42696 KB Output is correct
48 Correct 163 ms 47816 KB Output is correct
49 Correct 142 ms 46672 KB Output is correct
50 Correct 115 ms 37712 KB Output is correct
51 Correct 143 ms 40888 KB Output is correct
52 Correct 133 ms 42940 KB Output is correct
53 Correct 4 ms 24924 KB Output is correct
54 Correct 3 ms 24924 KB Output is correct
55 Correct 3 ms 22876 KB Output is correct
56 Correct 5 ms 25180 KB Output is correct
57 Correct 5 ms 25180 KB Output is correct
58 Correct 5 ms 25176 KB Output is correct
59 Correct 5 ms 25180 KB Output is correct
60 Correct 4 ms 25180 KB Output is correct
61 Correct 4 ms 25176 KB Output is correct
62 Correct 5 ms 25180 KB Output is correct
63 Correct 6 ms 25320 KB Output is correct
64 Correct 5 ms 25180 KB Output is correct
65 Correct 4 ms 25180 KB Output is correct
66 Correct 4 ms 25180 KB Output is correct
67 Correct 264 ms 70140 KB Output is correct
68 Correct 125 ms 39620 KB Output is correct
69 Correct 251 ms 64144 KB Output is correct
70 Correct 246 ms 59584 KB Output is correct
71 Correct 271 ms 65472 KB Output is correct
72 Correct 156 ms 40900 KB Output is correct
73 Correct 207 ms 58812 KB Output is correct
74 Correct 185 ms 58000 KB Output is correct
75 Correct 169 ms 40608 KB Output is correct
76 Correct 154 ms 40996 KB Output is correct
77 Correct 115 ms 39444 KB Output is correct
78 Correct 127 ms 39620 KB Output is correct
79 Correct 267 ms 77760 KB Output is correct
80 Correct 221 ms 76480 KB Output is correct
81 Correct 346 ms 64948 KB Output is correct
82 Correct 328 ms 59764 KB Output is correct
83 Correct 155 ms 40856 KB Output is correct
84 Correct 122 ms 39368 KB Output is correct
85 Correct 343 ms 65212 KB Output is correct
86 Correct 274 ms 77680 KB Output is correct
87 Correct 261 ms 77760 KB Output is correct
88 Correct 208 ms 59332 KB Output is correct
89 Correct 143 ms 43844 KB Output is correct
90 Correct 194 ms 43344 KB Output is correct
91 Correct 199 ms 42776 KB Output is correct
92 Correct 181 ms 42836 KB Output is correct
93 Correct 181 ms 42556 KB Output is correct
94 Correct 163 ms 42688 KB Output is correct
95 Correct 171 ms 47988 KB Output is correct
96 Correct 129 ms 46816 KB Output is correct
97 Correct 113 ms 37712 KB Output is correct
98 Correct 160 ms 40904 KB Output is correct
99 Correct 138 ms 42816 KB Output is correct
100 Correct 76 ms 29764 KB Output is correct
101 Correct 330 ms 59712 KB Output is correct
102 Correct 153 ms 41628 KB Output is correct
103 Correct 291 ms 58376 KB Output is correct
104 Correct 363 ms 65984 KB Output is correct