oj.uz

답안 #131120

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
131120 2019-07-16T14:56:55 Z nikolapesic2802 Uzastopni (COCI15_uzastopni) C++14
56 / 160
 19 ms 2040 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define D(x) cerr << #x << " is " << (x) << "\n";

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}

const int N=1e4+4,L=10;
vector<vector<int> > graf(N);
vector<int> v(N);
vector<pair<int,int> > calc(int tr,int par)
{
    vector<vector<int> > nxt(L);
    nxt[v[tr]].pb(v[tr]+1);
    for(auto p:graf[tr])
    {
        if(p==par)
            continue;
        auto sol=calc(p,tr);
        for(auto p:sol)
            if(p.f>v[tr]||p.s<=v[tr])
                nxt[p.f].pb(p.s);
    }
    vector<int> visited(L),no;
    vector<pair<int,int> > sol;
    for(int i=0;i<=v[tr];i++)
    {
        queue<int> q;
        q.push(i);
        visited[i]=1;
        no.pb(i);
        while(q.size())
        {
            int tr=q.front();
            q.pop();
            for(auto p:nxt[tr])
                if(!visited[p])
                    visited[p]=1,no.pb(p),q.push(p);
        }
        for(int j=1;j<(int)no.size();j++)
            if(no[j]>v[tr])
                sol.pb({i,no[j]});
        for(auto p:no)
            visited[p]=0;
        no.clear();
    }
    return sol;
}
int main()
{
	int n,a,b;
	scanf("%i",&n);
	for(int i=0;i<n;i++)
        scanf("%i",&v[i]),v[i]--;
    for(int i=1;i<n;i++)
        scanf("%i %i",&a,&b),a--,b--,graf[a].pb(b),graf[b].pb(a);
    auto sol=calc(0,0);
    printf("%i\n",sol.size());
    return 0;
}

Compilation message

uzastopni.cpp: In function 'int main()':
uzastopni.cpp:77:29: warning: format '%i' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' [-Wformat=]
     printf("%i\n",sol.size());
                   ~~~~~~~~~~^
uzastopni.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
uzastopni.cpp:73:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&v[i]),v[i]--;
         ~~~~~~~~~~~~~~~~~^~~~~~~
uzastopni.cpp:75:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i %i",&a,&b),a--,b--,graf[a].pb(b),graf[b].pb(a);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
56.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1148 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 3 ms 1144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Runtime error 3 ms 1144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 3 ms 1144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 3 ms 1016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 3 ms 1016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 3 ms 1020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 10 ms 2040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Correct 19 ms 1016 KB Output is correct
13 Correct 16 ms 1016 KB Output is correct
14 Runtime error 8 ms 1784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 8 ms 1784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 8 ms 1912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Correct 17 ms 1016 KB Output is correct
18 Correct 16 ms 1016 KB Output is correct
19 Runtime error 7 ms 1912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 7 ms 1788 KB Execution killed with signal 11 (could be triggered by violating memory limits)