oj.uz

Submission #623046

# Submission time Handle Problem Language Result Execution time Memory
623046 2022-08-05T06:24:31 Z radal Meetings (JOI19_meetings) C++17
29 / 100
 1998 ms 96256 KB 
#include <bits/stdc++.h>
#include "meetings.h"
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 2e3+10,mod = 998244353,inf = 1e9+10,sq = 700;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k /= 2;
    } 
    return z; 
}
int noob;
vector<int> tmp[N][N];
bool cmp(int u,int v){
    int x = Query(u,v,noob);
    if (x == u) return 1;
    return 0;
}
void dojob(vector<int> ve,int dep = 0){
    int n = ve.size();
    if (n == 1) return;
    if (n == 2){
        if (ve[1] < ve[0]) swap(ve[0],ve[1]);
        Bridge(ve[0],ve[1]);
        return;
    }
    int u = ve[0],v = ve[1];
    vector<int> path;
    tmp[u][dep].pb(u);
    tmp[v][dep].pb(v);
    rep(i,2,n){
        int w = ve[i];
        int x = Query(u,v,w);
        if (x == w) path.pb(w);
        tmp[x][dep].pb(w);
    }
    for (int w : ve) if (!tmp[w][dep].empty()){
        dojob(tmp[w][dep],dep+1);
        tmp[w][dep].clear();
    }
    if (path.empty()){
        Bridge(u,v);
        return;
    }
    noob = u;
    sort(all(path),cmp);
    int sz = path.size();
    Bridge(u,path[0]);
    Bridge(v,path.back());
    rep(i,1,sz){
        int x = path[i],y = path[i-1];
        if (x > y) swap(x,y);
        Bridge(x,y);
    }

}
void Solve(int n){
    vector<int> ve;
    rep(i,0,n) ve.pb(i);
    dojob(ve);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 95208 KB Output is correct
2 Correct 46 ms 95176 KB Output is correct
3 Correct 55 ms 95208 KB Output is correct
4 Correct 45 ms 95088 KB Output is correct
5 Correct 47 ms 95172 KB Output is correct
6 Correct 46 ms 95220 KB Output is correct
7 Correct 53 ms 95176 KB Output is correct
8 Correct 47 ms 95108 KB Output is correct
9 Correct 55 ms 95176 KB Output is correct
10 Correct 49 ms 95152 KB Output is correct
11 Correct 49 ms 95204 KB Output is correct
12 Correct 63 ms 95208 KB Output is correct
13 Correct 46 ms 95104 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 95208 KB Output is correct
2 Correct 46 ms 95176 KB Output is correct
3 Correct 55 ms 95208 KB Output is correct
4 Correct 45 ms 95088 KB Output is correct
5 Correct 47 ms 95172 KB Output is correct
6 Correct 46 ms 95220 KB Output is correct
7 Correct 53 ms 95176 KB Output is correct
8 Correct 47 ms 95108 KB Output is correct
9 Correct 55 ms 95176 KB Output is correct
10 Correct 49 ms 95152 KB Output is correct
11 Correct 49 ms 95204 KB Output is correct
12 Correct 63 ms 95208 KB Output is correct
13 Correct 46 ms 95104 KB Output is correct
14 Correct 47 ms 95116 KB Output is correct
15 Correct 46 ms 95196 KB Output is correct
16 Correct 47 ms 95136 KB Output is correct
17 Correct 48 ms 95148 KB Output is correct
18 Correct 47 ms 95136 KB Output is correct
19 Correct 51 ms 95172 KB Output is correct
20 Correct 50 ms 95104 KB Output is correct
21 Correct 47 ms 95200 KB Output is correct
22 Correct 48 ms 95192 KB Output is correct
23 Correct 48 ms 95104 KB Output is correct
24 Correct 52 ms 95160 KB Output is correct
25 Correct 54 ms 95208 KB Output is correct
26 Correct 54 ms 95312 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 95208 KB Output is correct
2 Correct 46 ms 95176 KB Output is correct
3 Correct 55 ms 95208 KB Output is correct
4 Correct 45 ms 95088 KB Output is correct
5 Correct 47 ms 95172 KB Output is correct
6 Correct 46 ms 95220 KB Output is correct
7 Correct 53 ms 95176 KB Output is correct
8 Correct 47 ms 95108 KB Output is correct
9 Correct 55 ms 95176 KB Output is correct
10 Correct 49 ms 95152 KB Output is correct
11 Correct 49 ms 95204 KB Output is correct
12 Correct 63 ms 95208 KB Output is correct
13 Correct 46 ms 95104 KB Output is correct
14 Correct 47 ms 95116 KB Output is correct
15 Correct 46 ms 95196 KB Output is correct
16 Correct 47 ms 95136 KB Output is correct
17 Correct 48 ms 95148 KB Output is correct
18 Correct 47 ms 95136 KB Output is correct
19 Correct 51 ms 95172 KB Output is correct
20 Correct 50 ms 95104 KB Output is correct
21 Correct 47 ms 95200 KB Output is correct
22 Correct 48 ms 95192 KB Output is correct
23 Correct 48 ms 95104 KB Output is correct
24 Correct 52 ms 95160 KB Output is correct
25 Correct 54 ms 95208 KB Output is correct
26 Correct 54 ms 95312 KB Output is correct
27 Correct 64 ms 95264 KB Output is correct
28 Correct 60 ms 95236 KB Output is correct
29 Correct 55 ms 95248 KB Output is correct
30 Correct 53 ms 95208 KB Output is correct
31 Correct 50 ms 95136 KB Output is correct
32 Correct 55 ms 95236 KB Output is correct
33 Correct 57 ms 95180 KB Output is correct
34 Correct 54 ms 95196 KB Output is correct
35 Correct 57 ms 95272 KB Output is correct
36 Correct 62 ms 95264 KB Output is correct
37 Correct 57 ms 95276 KB Output is correct
38 Correct 56 ms 95188 KB Output is correct
39 Correct 174 ms 95684 KB Output is correct

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 95588 KB Output is correct
2 Correct 467 ms 95592 KB Output is correct
3 Correct 454 ms 95548 KB Output is correct
4 Correct 429 ms 95588 KB Output is correct
5 Correct 306 ms 95568 KB Output is correct
6 Correct 337 ms 95508 KB Output is correct
7 Correct 400 ms 95680 KB Output is correct
8 Correct 434 ms 95560 KB Output is correct
9 Correct 440 ms 95712 KB Output is correct
10 Correct 421 ms 95712 KB Output is correct
11 Correct 486 ms 95608 KB Output is correct
12 Correct 408 ms 95596 KB Output is correct
13 Correct 305 ms 95600 KB Output is correct
14 Correct 435 ms 95772 KB Output is correct
15 Correct 311 ms 95660 KB Output is correct
16 Correct 365 ms 95664 KB Output is correct
17 Correct 700 ms 95720 KB Output is correct
18 Incorrect 1998 ms 96256 KB Wrong Answer [2]
19 Halted 0 ms 0 KB -