oj.uz

답안 #609501

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
609501 2022-07-27T16:26:52 Z AmirElarbi 통행료 (IOI18_highway) C++14
51 / 100
 318 ms 262144 KB 
#include <bits/stdc++.h>
#define vi vector<int>
#define gi greater<int>
#define gr greater
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e9
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 2e5+5
using namespace std;
const int MOD = 1e9+7;
const int nax = 1e5+5;
typedef complex<int> Point;
#define X real()
#define Y imag()
#include "highway.h"

vii adj[nax];
vi w;
int mxd= 0, dep[nax],m,nb;
ii par[nax];
void dfs(int u, int p){
    for(auto x : adj[u]){
        if(x.fi == p) continue;
        dep[x.fi] = dep[u]+1;
        par[x.fi] = {u,x.se};
        mxd = max(mxd, dep[x.fi]);
        dfs(x.fi,u);
    }
}
void color(int u, int p,int cl){
    for(auto x : adj[u]){
        if(x.fi == p) continue;
        w[x.se] = cl;
        color(x.fi, u, cl);
    }
}
void sub(int root){
    dep[root] = 0;
    par[root] = {root,root};
    dfs(root,root);
    vvi sm(mxd+1);
    w.clear();
    w.assign(m,0);
    for (int i = 0; i < nb; ++i)
    {
        sm[dep[i]].pb(i);
    }
    int totl = ask(w);
    int l = 0, r = mxd+1;
    while(l < r){
        w.clear();
        w.assign(m,0);
        int md = (l+r)/2;
        for(auto x : sm[md]){
            color(x,par[x].fi,1);
        }
        int qr = ask(w);
        if(qr == totl){
            r = md;
        } else {
            l = md+1;
        }
    }
    int dpanc = r;
    if(r == 0){
        answer(root,root);
        return;
    }
    l = 0, r = sm[dpanc].size();
    while(l< r){
        w.clear();
        w.assign(m,0);
        int md = (l+r)/2;
        for (int i = l; i <= md; ++i)
        {
            int u = sm[dpanc][i];
            w[par[u].se] = 1;
        }
        int qr = ask(w);
        if(qr==totl){
            l = md+1;
        } else {
            r = md;
        }
    }
    answer(root, sm[dpanc][r]);
}
void find_pair(int n, vi u, vi v, int a, int b) {
    m = u.size(), nb = n;
    for (int i = 0; i < m; ++i)
    {
        adj[u[i]].pb({v[i],i});
        adj[v[i]].pb({u[i],i});
    }
    dep[0] = 0;
    par[0] = {0,0};
    dfs(0,0);
    vvi sm(mxd+1);
    w.assign(m,0);
    for (int i = 0; i < n; ++i)
    {
        sm[dep[i]].pb(i);
    }
    int totl = ask(w);
    int l = 0, r = mxd+1;
    while(l < r){
        w.clear();
        w.assign(m,0);
        int md = (l+r)/2;
        for(auto x : sm[md]){
            color(x,par[x].fi,1);
        }
        int qr = ask(w);
        if(qr == totl){
            r = md;
        } else {
            l = md+1;
        }
    }
    int mxd = r;
    if(r == 0){
        answer(0,0);
        return;
    }
    l = 0, r = sm[mxd].size();
    while(l< r){
        w.clear();
        w.assign(m,0);
        int md = (l+r)/2;
        for (int i = l; i <= md; ++i)
        {
            int u = sm[mxd][i];
            w[par[u].se] = 1;
        }
        int qr = ask(w);
        if(qr==totl){
            l = md+1;
        } else {
            r = md;
        }
    }
    sub(sm[mxd][r]);
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 1 ms 2640 KB Output is correct
5 Correct 2 ms 2640 KB Output is correct
6 Correct 2 ms 2640 KB Output is correct
7 Correct 1 ms 2640 KB Output is correct
8 Correct 2 ms 2640 KB Output is correct
9 Correct 1 ms 2640 KB Output is correct
10 Correct 2 ms 2640 KB Output is correct
11 Correct 2 ms 2640 KB Output is correct
12 Correct 1 ms 2640 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 16 ms 3420 KB Output is correct
3 Correct 134 ms 9952 KB Output is correct
4 Correct 178 ms 9860 KB Output is correct
5 Correct 130 ms 9932 KB Output is correct
6 Correct 155 ms 9812 KB Output is correct
7 Correct 138 ms 9940 KB Output is correct
8 Correct 145 ms 9920 KB Output is correct
9 Correct 131 ms 9884 KB Output is correct
10 Correct 135 ms 9900 KB Output is correct
11 Correct 288 ms 12896 KB Output is correct
12 Correct 314 ms 14892 KB Output is correct
13 Correct 278 ms 13168 KB Output is correct
14 Correct 263 ms 13000 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 5112 KB Output is correct
2 Correct 24 ms 7352 KB Output is correct
3 Correct 38 ms 10024 KB Output is correct
4 Correct 173 ms 24108 KB Output is correct
5 Correct 128 ms 24172 KB Output is correct
6 Correct 129 ms 24748 KB Output is correct
7 Correct 162 ms 25132 KB Output is correct
8 Correct 144 ms 24204 KB Output is correct
9 Correct 112 ms 24556 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2748 KB Output is correct
2 Correct 14 ms 3420 KB Output is correct
3 Correct 116 ms 8308 KB Output is correct
4 Correct 168 ms 9788 KB Output is correct
5 Correct 200 ms 9876 KB Output is correct
6 Correct 179 ms 9848 KB Output is correct
7 Correct 176 ms 9880 KB Output is correct
8 Correct 202 ms 9876 KB Output is correct
9 Correct 167 ms 9896 KB Output is correct
10 Correct 275 ms 9856 KB Output is correct
11 Correct 259 ms 12304 KB Output is correct
12 Correct 217 ms 14396 KB Output is correct
13 Correct 305 ms 13476 KB Output is correct
14 Correct 288 ms 14428 KB Output is correct
15 Correct 143 ms 9824 KB Output is correct
16 Correct 150 ms 9860 KB Output is correct
17 Correct 205 ms 13804 KB Output is correct
18 Correct 318 ms 13732 KB Output is correct
19 Correct 149 ms 9864 KB Output is correct
20 Correct 316 ms 15740 KB Output is correct
21 Correct 108 ms 10472 KB Output is correct
22 Correct 145 ms 10544 KB Output is correct
23 Correct 137 ms 10172 KB Output is correct
24 Correct 162 ms 11656 KB Output is correct
25 Correct 236 ms 23240 KB Output is correct

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 233 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 202 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -