oj.uz

답안 #1068115

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1068115 2024-08-21T07:47:33 Z Sir_Ahmed_Imran 통행료 (IOI18_highway) C++17
18 / 100
 114 ms 20172 KB 
                            ///~~~LOTA~~~///
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define append push_back
#define add insert
#define nl '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define terminator main
#define N 90000
int d;
int ve[N];
int par[N];
int dept[N];
vector<pii> e[N];
vector<int> x[N];
void dfs(int v,int u){
    d=max(d,dept[v]);
    x[dept[v]].append(v);
    for(auto& i:e[v]){
        if(i.ff==u)
            continue;
        dept[i.ff]=dept[v]+1;
        ve[i.ff]=i.ss;
        par[i.ff]=v;
        dfs(i.ff,v);
    }
}
void find_pair(int n,vector<int> v,vector<int> u,int a,int b){
    ll m,o,p,q,r,s,t;
    vector<int> h;
    for(int i=1;i<n;i++)
        h.append(0);
    for(int i=m=d=0;i<n-1;i++){
        e[v[i]].append({u[i],i});
        e[u[i]].append({v[i],i});
    }
    o=ask(h);
    dfs(0,-1);
    for(int i=65536;i>0;i/=2){
        if(m+i>d) continue;
        for(int j=1;j<=m+i;j++)
            for(auto& k:x[j])
                h[ve[k]]=1;
        r=ask(h);
        for(int j=1;j<=m+i;j++)
            for(auto& k:x[j])
                h[ve[k]]=0;
        if(r==o) m+=i;
    }
    p=q=m;
    for(int i=65536;i>0;i/=2){
        if(p+i<=d){
            for(auto& j:x[p+i])
                h[ve[j]]=1;
            r=ask(h);
            for(auto& j:x[p+i])
                h[ve[j]]=0;
            if(r-o==2*(b-a)) p+=i;
        }
        if(q+i<=d){
            for(auto& j:x[q+i])
                h[ve[j]]=1;
            r=ask(h);
            for(auto& j:x[q+i])
                h[ve[j]]=0;
            if(r>o) q+=i;
        }
    }
    s=t=0;
    for(int i=65536;i>0;i/=2){
        if(s+i>x[q].size())
            continue;
        for(int j=0;j<s+i;j++)
            h[ve[x[q][j]]]=1;
        r=ask(h);
        for(int j=0;j<s+i;j++)
            h[ve[x[q][j]]]=0;
        if(r==o) s+=i;
    }
    s=q=x[q][s];
    while(dept[q]>p)
        q=par[q];
    if(p==m){
        answer(s,q);
        return;
    }
    for(int i=65536;i>0;i/=2){
        if(t+i>x[p].size())
            continue;
        for(int j=0;j<t+i;j++)
            h[ve[x[p][j]]]=1;
        h[ve[q]]=0;
        r=ask(h);
        for(int j=0;j<t+i;j++)
            h[ve[x[p][j]]]=0;
        if(r==o) t+=i;
    }
    t=x[p][t];
    answer(s,t);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:79:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         if(s+i>x[q].size())
      |            ~~~^~~~~~~~~~~~
highway.cpp:96:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         if(t+i>x[p].size())
      |            ~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 9 ms 5260 KB Output is correct
3 Correct 93 ms 11368 KB Output is correct
4 Correct 76 ms 11400 KB Output is correct
5 Correct 81 ms 11396 KB Output is correct
6 Correct 74 ms 11352 KB Output is correct
7 Correct 76 ms 11400 KB Output is correct
8 Correct 80 ms 11440 KB Output is correct
9 Correct 77 ms 11420 KB Output is correct
10 Correct 80 ms 11376 KB Output is correct
11 Correct 83 ms 12744 KB Output is correct
12 Correct 88 ms 13884 KB Output is correct
13 Correct 88 ms 12996 KB Output is correct
14 Correct 96 ms 12184 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 6232 KB Output is correct
2 Correct 18 ms 8024 KB Output is correct
3 Correct 26 ms 9772 KB Output is correct
4 Correct 86 ms 20076 KB Output is correct
5 Correct 77 ms 20092 KB Output is correct
6 Correct 74 ms 20160 KB Output is correct
7 Correct 85 ms 20172 KB Output is correct
8 Correct 88 ms 20168 KB Output is correct
9 Correct 78 ms 20164 KB Output is correct

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 9 ms 5208 KB Output is correct
3 Correct 62 ms 9888 KB Output is correct
4 Correct 80 ms 11772 KB Output is correct
5 Correct 83 ms 11408 KB Output is correct
6 Correct 84 ms 11408 KB Output is correct
7 Correct 93 ms 12164 KB Output is correct
8 Correct 81 ms 11384 KB Output is correct
9 Correct 80 ms 11380 KB Output is correct
10 Correct 86 ms 11384 KB Output is correct
11 Correct 95 ms 12092 KB Output is correct
12 Correct 94 ms 13996 KB Output is correct
13 Correct 110 ms 13256 KB Output is correct
14 Correct 96 ms 13768 KB Output is correct
15 Correct 78 ms 11400 KB Output is correct
16 Correct 76 ms 11384 KB Output is correct
17 Correct 109 ms 13468 KB Output is correct
18 Correct 95 ms 12848 KB Output is correct
19 Correct 80 ms 11364 KB Output is correct
20 Correct 98 ms 14652 KB Output is correct
21 Correct 74 ms 11876 KB Output is correct
22 Correct 78 ms 11896 KB Output is correct
23 Correct 91 ms 12088 KB Output is correct
24 Incorrect 114 ms 12676 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 5208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 5208 KB Incorrect
2 Halted 0 ms 0 KB -