Submission #1650381


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

using pi = pair<int,int>;

const int N = 100000;
const ll INF = LLONG_MAX/3;

vector<int> G[N];
vector<int> ew;
void dfs(int v)
{
    ew.pb(v);
    for(int c:G[v]) dfs(c);
    ew.pb(v);
}

int main()
{
    int n;
    scanf(" %d", &n);
    vector<int> a(n);
    rep(i,n) scanf(" %d", &a[i]);

    vector<bool> candidate(n,true);
    rep(i,n-1)
    {
        int s,t;
        scanf(" %d %d", &s, &t);
        G[s].pb(t);
        candidate[t] = false;
    }

    int root = 0;
    rep(i,n)if(candidate[i]) root = i;
    dfs(root);

    vector<ll> val(n,INF);
    set<int> v;

    vector<int> ct(n);
    rep(i,ew.size())
    {
        int id = ew[i];
        if(ct[id]==0)
        {
            auto itr = v.lower_bound(a[id]);
            if(itr!=v.end())
            {
                int x = *itr;
                if(abs(a[id]-x)<abs(val[id]-x)) val[id] = x;
            }
            if(itr!=v.begin())
            {
                --itr;
                int x = *itr;
                if(abs(a[id]-x)<abs(val[id]-x)) val[id] = x;
            }
        }
        else v.insert(a[id]);
        ++ct[id];
    }

    v.clear();
    reverse(all(ew));
    ct = vector<int>(n,0);
    rep(i,ew.size())
    {
        int id = ew[i];
        if(ct[id]==0)
        {
            auto itr = v.lower_bound(a[id]);
            if(itr!=v.end())
            {
                int x = *itr;
                if(abs(a[id]-x)<abs(val[id]-x)) val[id] = x;
            }
            if(itr!=v.begin())
            {
                --itr;
                int x = *itr;
                if(abs(a[id]-x)<abs(val[id]-x)) val[id] = x;
            }
        }
        else v.insert(a[id]);
        ++ct[id];
    }

    rep(i,n) printf("%lld\n", val[i]==INF?-1:val[i]);
    return 0;
}

Submission Info

Submission Time
Task I - 支配と友好
User imulan
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2348 Byte
Status WA
Exec Time 171 ms
Memory 17708 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:30:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %d", &n);
                     ^
./Main.cpp:32:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     rep(i,n) scanf(" %d", &a[i]);
                                 ^
./Main.cpp:38:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %d %d", &s, &t);
                                ^

Judge Result

Set Name All
Score / Max Score 0 / 200
Status
AC × 13
WA × 32
Set Name Test Cases
All sample01, sample02, sample03, binary00, binary01, binary02, binary03, hand00, line00, line01, line02, random00, random01, random02, random03, random04, random05, random06, random07, random08, sample01, sample02, sample03, star00, star01, star02, ternary00, ternary01, ternary02, ternary03, thin00, thin01, thin02, thin03, thin04, thin05, thin06, thin07, uniform00, uniform01, uniform02, uniform03, uniform04, uniform05, uniform06
Case Name Status Exec Time Memory
binary00 AC 73 ms 7156 KB
binary01 WA 106 ms 7412 KB
binary02 WA 153 ms 11968 KB
binary03 WA 150 ms 12204 KB
hand00 AC 112 ms 15916 KB
line00 AC 69 ms 13428 KB
line01 AC 95 ms 13556 KB
line02 AC 133 ms 17708 KB
random00 AC 62 ms 7160 KB
random01 AC 70 ms 7288 KB
random02 AC 85 ms 7288 KB
random03 WA 104 ms 7544 KB
random04 WA 141 ms 10092 KB
random05 WA 149 ms 11664 KB
random06 WA 149 ms 11972 KB
random07 WA 150 ms 12080 KB
random08 WA 160 ms 12208 KB
sample01 WA 3 ms 2560 KB
sample02 AC 3 ms 2560 KB
sample03 WA 3 ms 2560 KB
star00 AC 56 ms 6008 KB
star01 AC 92 ms 6264 KB
star02 WA 141 ms 10928 KB
ternary00 AC 67 ms 6644 KB
ternary01 WA 104 ms 6900 KB
ternary02 WA 146 ms 11460 KB
ternary03 WA 149 ms 11692 KB
thin00 WA 72 ms 9460 KB
thin01 WA 70 ms 8180 KB
thin02 WA 112 ms 9844 KB
thin03 WA 108 ms 8436 KB
thin04 WA 171 ms 14276 KB
thin05 WA 149 ms 12992 KB
thin06 WA 156 ms 14508 KB
thin07 WA 153 ms 13228 KB
uniform00 WA 155 ms 11312 KB
uniform01 WA 143 ms 11632 KB
uniform02 WA 157 ms 11380 KB
uniform03 WA 153 ms 11276 KB
uniform04 WA 155 ms 11108 KB
uniform05 WA 149 ms 11104 KB
uniform06 WA 145 ms 10976 KB