oj.uz

Submission #893038

# Submission time Handle Problem Language Result Execution time Memory
893038 2023-12-26T11:46:37 Z alexander707070 Security Guard (JOI23_guard) C++14
58 / 100
 4000 ms 56680 KB 
#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;

struct edge{
    int from,to,cost;
};

bool cmp(edge fr,edge sc){
    return fr.cost<sc.cost;
}

int n,m,q,a,b,s[MAXN],c,d;
vector<edge> w;
unordered_set<int> tree[MAXN];
long long ans;
bool ok;

int dsu[MAXN],sz[MAXN],maxs;

int root(int x){
    if(dsu[x]==x)return x;
    dsu[x]=root(dsu[x]);
    return dsu[x];
}

void mergev(int x,int y){
    int rootx=root(x);
    int rooty=root(y);

    if(sz[rooty]>sz[rootx])swap(rootx,rooty);
    sz[rootx]+=sz[rooty];
    dsu[rooty]=dsu[rootx];
}

int best(int x,int y){
    if(s[x]<s[y])return x;
    return y;
}

int dfs(int x,int p){
    int res=x;

    for(int e:tree[x]){
        if(e==p)continue;
        res=best(res,dfs(e,x));
    }

    return res;
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m>>q;

    for(int i=1;i<=n;i++){
        cin>>s[i];
        ans-=s[i];
        maxs=max(maxs,s[i]);

        dsu[i]=i; sz[i]=1;
    }

    for(int i=1;i<=m;i++){
        cin>>a>>b;
        w.push_back({a,b,s[a]+s[b]});
    }

    sort(w.begin(),w.end(),cmp);

    for(int i=0;i<w.size();i++){
        if(root(w[i].from)==root(w[i].to))continue;
        mergev(w[i].from,w[i].to);

        tree[w[i].from].insert(w[i].to);
        tree[w[i].to].insert(w[i].from);

        ans+=s[w[i].from]+s[w[i].to];
    }

    ans+=maxs;

    cout<<ans<<"\n";

    for(int i=1;i<=q;i++){

        maxs=0;

        for(int f=1;f<=n and !ok;f++){
            for(int e:tree[f]){
                if(e<f)continue;

                int sx=dfs(f,e);
                int sy=dfs(e,f);
                
                if(s[f]+s[e]-s[sx]-s[sy]>maxs){
                    maxs=s[f]+s[e]-s[sx]-s[sy];
                    a=f; b=e; c=sx; d=sy;
                }
            }
        }

        if(maxs!=0){
            ans-=maxs;
            tree[a].erase(b);
            tree[b].erase(a);

            tree[c].insert(d);
            tree[d].insert(c);
        }else ok=true;

        if(!ok and i>=n)cout<<1/0;

        cout<<ans<<"\n";
    }


    return 0;
}

Compilation message

guard.cpp: In function 'int main()':
guard.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~
guard.cpp:116:32: warning: division by zero [-Wdiv-by-zero]
  116 |         if(!ok and i>=n)cout<<1/0;
      |                               ~^~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 88 ms 50508 KB Output is correct
3 Correct 85 ms 50512 KB Output is correct
4 Correct 129 ms 50632 KB Output is correct
5 Correct 112 ms 50364 KB Output is correct
6 Correct 110 ms 50620 KB Output is correct
7 Correct 120 ms 50300 KB Output is correct
8 Correct 3 ms 12636 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 88 ms 50508 KB Output is correct
3 Correct 85 ms 50512 KB Output is correct
4 Correct 129 ms 50632 KB Output is correct
5 Correct 112 ms 50364 KB Output is correct
6 Correct 110 ms 50620 KB Output is correct
7 Correct 120 ms 50300 KB Output is correct
8 Correct 3 ms 12636 KB Output is correct
9 Correct 3 ms 12636 KB Output is correct
10 Correct 173 ms 50552 KB Output is correct
11 Correct 92 ms 50524 KB Output is correct
12 Correct 94 ms 50532 KB Output is correct
13 Correct 86 ms 50368 KB Output is correct
14 Correct 172 ms 51108 KB Output is correct
15 Correct 162 ms 50880 KB Output is correct
16 Correct 163 ms 50360 KB Output is correct
17 Correct 174 ms 50620 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 88 ms 50508 KB Output is correct
3 Correct 85 ms 50512 KB Output is correct
4 Correct 129 ms 50632 KB Output is correct
5 Correct 112 ms 50364 KB Output is correct
6 Correct 110 ms 50620 KB Output is correct
7 Correct 120 ms 50300 KB Output is correct
8 Correct 3 ms 12636 KB Output is correct
9 Correct 3 ms 12636 KB Output is correct
10 Correct 173 ms 50552 KB Output is correct
11 Correct 92 ms 50524 KB Output is correct
12 Correct 94 ms 50532 KB Output is correct
13 Correct 86 ms 50368 KB Output is correct
14 Correct 172 ms 51108 KB Output is correct
15 Correct 162 ms 50880 KB Output is correct
16 Correct 163 ms 50360 KB Output is correct
17 Correct 174 ms 50620 KB Output is correct
18 Correct 3 ms 12636 KB Output is correct
19 Correct 201 ms 50440 KB Output is correct
20 Correct 203 ms 50360 KB Output is correct
21 Correct 209 ms 50832 KB Output is correct
22 Correct 216 ms 50476 KB Output is correct
23 Correct 217 ms 52668 KB Output is correct
24 Correct 244 ms 52216 KB Output is correct
25 Correct 226 ms 53252 KB Output is correct
26 Correct 259 ms 53252 KB Output is correct
27 Correct 228 ms 53692 KB Output is correct
28 Correct 216 ms 50708 KB Output is correct
29 Correct 266 ms 51044 KB Output is correct
30 Correct 267 ms 51904 KB Output is correct
31 Correct 188 ms 53184 KB Output is correct
32 Correct 236 ms 51128 KB Output is correct
33 Correct 186 ms 51132 KB Output is correct
34 Correct 181 ms 50368 KB Output is correct
35 Correct 180 ms 50344 KB Output is correct
36 Correct 205 ms 52672 KB Output is correct
37 Correct 262 ms 52668 KB Output is correct
38 Correct 208 ms 51136 KB Output is correct
39 Correct 204 ms 52200 KB Output is correct
40 Correct 173 ms 51124 KB Output is correct
41 Correct 149 ms 50368 KB Output is correct
42 Correct 161 ms 50688 KB Output is correct
43 Correct 210 ms 50424 KB Output is correct
44 Correct 198 ms 50304 KB Output is correct
45 Correct 205 ms 50620 KB Output is correct
46 Correct 190 ms 51136 KB Output is correct
47 Correct 189 ms 50452 KB Output is correct
48 Correct 203 ms 50560 KB Output is correct
49 Correct 162 ms 50376 KB Output is correct
50 Correct 161 ms 50336 KB Output is correct
51 Correct 202 ms 50628 KB Output is correct
52 Correct 185 ms 50364 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 88 ms 50508 KB Output is correct
3 Correct 85 ms 50512 KB Output is correct
4 Correct 129 ms 50632 KB Output is correct
5 Correct 112 ms 50364 KB Output is correct
6 Correct 110 ms 50620 KB Output is correct
7 Correct 120 ms 50300 KB Output is correct
8 Correct 3 ms 12636 KB Output is correct
9 Correct 3 ms 12636 KB Output is correct
10 Correct 173 ms 50552 KB Output is correct
11 Correct 92 ms 50524 KB Output is correct
12 Correct 94 ms 50532 KB Output is correct
13 Correct 86 ms 50368 KB Output is correct
14 Correct 172 ms 51108 KB Output is correct
15 Correct 162 ms 50880 KB Output is correct
16 Correct 163 ms 50360 KB Output is correct
17 Correct 174 ms 50620 KB Output is correct
18 Correct 3 ms 12636 KB Output is correct
19 Correct 201 ms 50440 KB Output is correct
20 Correct 203 ms 50360 KB Output is correct
21 Correct 209 ms 50832 KB Output is correct
22 Correct 216 ms 50476 KB Output is correct
23 Correct 217 ms 52668 KB Output is correct
24 Correct 244 ms 52216 KB Output is correct
25 Correct 226 ms 53252 KB Output is correct
26 Correct 259 ms 53252 KB Output is correct
27 Correct 228 ms 53692 KB Output is correct
28 Correct 216 ms 50708 KB Output is correct
29 Correct 266 ms 51044 KB Output is correct
30 Correct 267 ms 51904 KB Output is correct
31 Correct 188 ms 53184 KB Output is correct
32 Correct 236 ms 51128 KB Output is correct
33 Correct 186 ms 51132 KB Output is correct
34 Correct 181 ms 50368 KB Output is correct
35 Correct 180 ms 50344 KB Output is correct
36 Correct 205 ms 52672 KB Output is correct
37 Correct 262 ms 52668 KB Output is correct
38 Correct 208 ms 51136 KB Output is correct
39 Correct 204 ms 52200 KB Output is correct
40 Correct 173 ms 51124 KB Output is correct
41 Correct 149 ms 50368 KB Output is correct
42 Correct 161 ms 50688 KB Output is correct
43 Correct 210 ms 50424 KB Output is correct
44 Correct 198 ms 50304 KB Output is correct
45 Correct 205 ms 50620 KB Output is correct
46 Correct 190 ms 51136 KB Output is correct
47 Correct 189 ms 50452 KB Output is correct
48 Correct 203 ms 50560 KB Output is correct
49 Correct 162 ms 50376 KB Output is correct
50 Correct 161 ms 50336 KB Output is correct
51 Correct 202 ms 50628 KB Output is correct
52 Correct 185 ms 50364 KB Output is correct
53 Correct 3 ms 12636 KB Output is correct
54 Correct 203 ms 50624 KB Output is correct
55 Correct 219 ms 50628 KB Output is correct
56 Correct 216 ms 51632 KB Output is correct
57 Correct 266 ms 53680 KB Output is correct
58 Correct 266 ms 55220 KB Output is correct
59 Correct 299 ms 55992 KB Output is correct
60 Correct 314 ms 55588 KB Output is correct
61 Correct 330 ms 56680 KB Output is correct
62 Correct 272 ms 55912 KB Output is correct
63 Correct 252 ms 50828 KB Output is correct
64 Correct 315 ms 53248 KB Output is correct
65 Correct 331 ms 55476 KB Output is correct
66 Correct 314 ms 55476 KB Output is correct
67 Correct 334 ms 54764 KB Output is correct
68 Correct 210 ms 50364 KB Output is correct
69 Correct 233 ms 52532 KB Output is correct
70 Correct 206 ms 50716 KB Output is correct
71 Correct 236 ms 52500 KB Output is correct
72 Correct 300 ms 52812 KB Output is correct
73 Correct 223 ms 51192 KB Output is correct
74 Correct 205 ms 51812 KB Output is correct
75 Correct 247 ms 51396 KB Output is correct
76 Correct 155 ms 50364 KB Output is correct
77 Correct 154 ms 50540 KB Output is correct
78 Correct 211 ms 51092 KB Output is correct
79 Correct 270 ms 53544 KB Output is correct
80 Correct 213 ms 51176 KB Output is correct
81 Correct 263 ms 53340 KB Output is correct
82 Correct 291 ms 53468 KB Output is correct
83 Correct 294 ms 53284 KB Output is correct
84 Correct 261 ms 52920 KB Output is correct
85 Correct 194 ms 50516 KB Output is correct
86 Correct 228 ms 50536 KB Output is correct
87 Correct 205 ms 50368 KB Output is correct
88 Correct 284 ms 53940 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 3 ms 12632 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 12636 KB Output is correct
8 Correct 16 ms 14812 KB Output is correct
9 Correct 16 ms 14936 KB Output is correct
10 Correct 14 ms 14684 KB Output is correct
11 Correct 15 ms 14940 KB Output is correct
12 Correct 17 ms 15448 KB Output is correct
13 Correct 22 ms 14896 KB Output is correct
14 Correct 15 ms 14936 KB Output is correct
15 Correct 16 ms 14940 KB Output is correct
16 Correct 15 ms 14936 KB Output is correct

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 3 ms 12632 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 12636 KB Output is correct
8 Correct 16 ms 14812 KB Output is correct
9 Correct 16 ms 14936 KB Output is correct
10 Correct 14 ms 14684 KB Output is correct
11 Correct 15 ms 14940 KB Output is correct
12 Correct 17 ms 15448 KB Output is correct
13 Correct 22 ms 14896 KB Output is correct
14 Correct 15 ms 14936 KB Output is correct
15 Correct 16 ms 14940 KB Output is correct
16 Correct 15 ms 14936 KB Output is correct
17 Execution timed out 4021 ms 13656 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 88 ms 50508 KB Output is correct
3 Correct 85 ms 50512 KB Output is correct
4 Correct 129 ms 50632 KB Output is correct
5 Correct 112 ms 50364 KB Output is correct
6 Correct 110 ms 50620 KB Output is correct
7 Correct 120 ms 50300 KB Output is correct
8 Correct 3 ms 12636 KB Output is correct
9 Correct 3 ms 12636 KB Output is correct
10 Correct 173 ms 50552 KB Output is correct
11 Correct 92 ms 50524 KB Output is correct
12 Correct 94 ms 50532 KB Output is correct
13 Correct 86 ms 50368 KB Output is correct
14 Correct 172 ms 51108 KB Output is correct
15 Correct 162 ms 50880 KB Output is correct
16 Correct 163 ms 50360 KB Output is correct
17 Correct 174 ms 50620 KB Output is correct
18 Correct 3 ms 12636 KB Output is correct
19 Correct 201 ms 50440 KB Output is correct
20 Correct 203 ms 50360 KB Output is correct
21 Correct 209 ms 50832 KB Output is correct
22 Correct 216 ms 50476 KB Output is correct
23 Correct 217 ms 52668 KB Output is correct
24 Correct 244 ms 52216 KB Output is correct
25 Correct 226 ms 53252 KB Output is correct
26 Correct 259 ms 53252 KB Output is correct
27 Correct 228 ms 53692 KB Output is correct
28 Correct 216 ms 50708 KB Output is correct
29 Correct 266 ms 51044 KB Output is correct
30 Correct 267 ms 51904 KB Output is correct
31 Correct 188 ms 53184 KB Output is correct
32 Correct 236 ms 51128 KB Output is correct
33 Correct 186 ms 51132 KB Output is correct
34 Correct 181 ms 50368 KB Output is correct
35 Correct 180 ms 50344 KB Output is correct
36 Correct 205 ms 52672 KB Output is correct
37 Correct 262 ms 52668 KB Output is correct
38 Correct 208 ms 51136 KB Output is correct
39 Correct 204 ms 52200 KB Output is correct
40 Correct 173 ms 51124 KB Output is correct
41 Correct 149 ms 50368 KB Output is correct
42 Correct 161 ms 50688 KB Output is correct
43 Correct 210 ms 50424 KB Output is correct
44 Correct 198 ms 50304 KB Output is correct
45 Correct 205 ms 50620 KB Output is correct
46 Correct 190 ms 51136 KB Output is correct
47 Correct 189 ms 50452 KB Output is correct
48 Correct 203 ms 50560 KB Output is correct
49 Correct 162 ms 50376 KB Output is correct
50 Correct 161 ms 50336 KB Output is correct
51 Correct 202 ms 50628 KB Output is correct
52 Correct 185 ms 50364 KB Output is correct
53 Correct 3 ms 12636 KB Output is correct
54 Correct 203 ms 50624 KB Output is correct
55 Correct 219 ms 50628 KB Output is correct
56 Correct 216 ms 51632 KB Output is correct
57 Correct 266 ms 53680 KB Output is correct
58 Correct 266 ms 55220 KB Output is correct
59 Correct 299 ms 55992 KB Output is correct
60 Correct 314 ms 55588 KB Output is correct
61 Correct 330 ms 56680 KB Output is correct
62 Correct 272 ms 55912 KB Output is correct
63 Correct 252 ms 50828 KB Output is correct
64 Correct 315 ms 53248 KB Output is correct
65 Correct 331 ms 55476 KB Output is correct
66 Correct 314 ms 55476 KB Output is correct
67 Correct 334 ms 54764 KB Output is correct
68 Correct 210 ms 50364 KB Output is correct
69 Correct 233 ms 52532 KB Output is correct
70 Correct 206 ms 50716 KB Output is correct
71 Correct 236 ms 52500 KB Output is correct
72 Correct 300 ms 52812 KB Output is correct
73 Correct 223 ms 51192 KB Output is correct
74 Correct 205 ms 51812 KB Output is correct
75 Correct 247 ms 51396 KB Output is correct
76 Correct 155 ms 50364 KB Output is correct
77 Correct 154 ms 50540 KB Output is correct
78 Correct 211 ms 51092 KB Output is correct
79 Correct 270 ms 53544 KB Output is correct
80 Correct 213 ms 51176 KB Output is correct
81 Correct 263 ms 53340 KB Output is correct
82 Correct 291 ms 53468 KB Output is correct
83 Correct 294 ms 53284 KB Output is correct
84 Correct 261 ms 52920 KB Output is correct
85 Correct 194 ms 50516 KB Output is correct
86 Correct 228 ms 50536 KB Output is correct
87 Correct 205 ms 50368 KB Output is correct
88 Correct 284 ms 53940 KB Output is correct
89 Correct 3 ms 12632 KB Output is correct
90 Correct 3 ms 12632 KB Output is correct
91 Correct 3 ms 12636 KB Output is correct
92 Correct 3 ms 12636 KB Output is correct
93 Correct 3 ms 12636 KB Output is correct
94 Correct 3 ms 12636 KB Output is correct
95 Correct 3 ms 12636 KB Output is correct
96 Correct 16 ms 14812 KB Output is correct
97 Correct 16 ms 14936 KB Output is correct
98 Correct 14 ms 14684 KB Output is correct
99 Correct 15 ms 14940 KB Output is correct
100 Correct 17 ms 15448 KB Output is correct
101 Correct 22 ms 14896 KB Output is correct
102 Correct 15 ms 14936 KB Output is correct
103 Correct 16 ms 14940 KB Output is correct
104 Correct 15 ms 14936 KB Output is correct
105 Execution timed out 4021 ms 13656 KB Time limit exceeded
106 Halted 0 ms 0 KB -