Submission #1186700
Source Code Expand
#include <algorithm> #include <array> #include <bitset> #include <cassert> #include <cmath> #include <complex> #include <cstdio> #include <cstring> #include <deque> #include <functional> #include <iomanip> #include <locale> #include <iostream> #include <map> #include <memory> #include <new> #include <numeric> #include <queue> #include <random> #include <set> #include <sstream> #include <string> #include <tuple> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> #define REP(i,n) for(int i=0;i<(int)(n);i++) #define ALL(x) (x).begin(),(x).end() using namespace std; using ll = long long; using ld = long double; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template <typename T> int len(const T &x) { return x.size(); } template<typename T> vector<T> table(int n, T v) { return vector<T>(n, v); } template <class... Args> auto table(int n, Args... args) { auto val = table(args...); return vector<decltype(val)>(n, move(val)); } struct yes_no : numpunct<char> { string_type do_truename() const { return "Yes"; } string_type do_falsename() const { return "No"; } }; vector<int> g[5010]; int dp[5010]; void solve(ll N, vector<ll> A, vector<ll> a, vector<ll> b) { REP(i,N-1) { int s = a[i] - 1, t = b[i] - 1; g[s].push_back(t); g[t].push_back(s); } vector<pair<ll,int>> vec; REP(i,N) vec.emplace_back(A[i], i); sort(ALL(vec)); vector<vector<int>> ord; vector<int> tmp; REP(i,N) { tmp.push_back(vec[i].second); if (i == N - 1 || vec[i].first != vec[i+1].first) { ord.push_back(tmp); tmp.clear(); } } for (auto v: ord) { vector<int> upd; for (int i: v) { bool win = false; for (int j: g[i]) { if (dp[j]) win = true; } if (!win) upd.push_back(i); } for (int i: upd) dp[i] = 1; } vector<int> res; REP(i,N) if (!dp[i]) res.push_back(i); REP(i,res.size()) cout << res[i] + 1 << " \n"[i == len(res) - 1]; if (res.empty()) cout << endl; } int main() { locale loc(locale(), new yes_no); cout << boolalpha << setprecision(12) << fixed; cout.imbue(loc); ll N; scanf("%lld", &N); vector<ll> A(N-1+1); vector<ll> a((N-1)-1+1); vector<ll> b((N-1)-1+1); for (int i = 0 ; i <= N-1 ; i++) { scanf("%lld", &A[i]); } for (int i = 0 ; i <= (N-1)-1 ; i++) { scanf("%lld", &a[i]); scanf("%lld", &b[i]); } solve(N, A, a, b); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Tree Game |
User | asi1024 |
Language | C++14 (GCC 5.4.1) |
Score | 1600 |
Code Size | 2625 Byte |
Status | AC |
Exec Time | 3 ms |
Memory | 896 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:98:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%lld", &N); ^ ./Main.cpp:103:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%lld", &A[i]); ^ ./Main.cpp:106:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%lld", &a[i]); ^ ./Main.cpp:107:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%lld", &b[i]); ^
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1600 / 1600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample1.txt, sample2.txt, sample3.txt |
All | sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in4.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in46.txt, in47.txt, in48.txt, in49.txt, in5.txt, in50.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
in1.txt | AC | 3 ms | 896 KB |
in10.txt | AC | 3 ms | 896 KB |
in11.txt | AC | 3 ms | 896 KB |
in12.txt | AC | 2 ms | 512 KB |
in13.txt | AC | 2 ms | 512 KB |
in14.txt | AC | 3 ms | 896 KB |
in15.txt | AC | 3 ms | 896 KB |
in16.txt | AC | 3 ms | 896 KB |
in17.txt | AC | 3 ms | 896 KB |
in18.txt | AC | 3 ms | 896 KB |
in19.txt | AC | 3 ms | 896 KB |
in2.txt | AC | 3 ms | 896 KB |
in20.txt | AC | 3 ms | 896 KB |
in21.txt | AC | 3 ms | 896 KB |
in22.txt | AC | 3 ms | 896 KB |
in23.txt | AC | 3 ms | 896 KB |
in24.txt | AC | 3 ms | 896 KB |
in25.txt | AC | 3 ms | 896 KB |
in26.txt | AC | 3 ms | 896 KB |
in27.txt | AC | 3 ms | 896 KB |
in28.txt | AC | 3 ms | 896 KB |
in29.txt | AC | 3 ms | 896 KB |
in3.txt | AC | 3 ms | 896 KB |
in30.txt | AC | 3 ms | 896 KB |
in31.txt | AC | 3 ms | 896 KB |
in32.txt | AC | 3 ms | 896 KB |
in33.txt | AC | 3 ms | 896 KB |
in34.txt | AC | 3 ms | 896 KB |
in35.txt | AC | 3 ms | 896 KB |
in36.txt | AC | 1 ms | 384 KB |
in37.txt | AC | 1 ms | 384 KB |
in38.txt | AC | 1 ms | 384 KB |
in39.txt | AC | 1 ms | 384 KB |
in4.txt | AC | 3 ms | 896 KB |
in40.txt | AC | 3 ms | 768 KB |
in41.txt | AC | 3 ms | 768 KB |
in42.txt | AC | 3 ms | 768 KB |
in43.txt | AC | 3 ms | 768 KB |
in44.txt | AC | 3 ms | 768 KB |
in45.txt | AC | 3 ms | 768 KB |
in46.txt | AC | 3 ms | 768 KB |
in47.txt | AC | 3 ms | 768 KB |
in48.txt | AC | 3 ms | 768 KB |
in49.txt | AC | 3 ms | 768 KB |
in5.txt | AC | 3 ms | 640 KB |
in50.txt | AC | 3 ms | 768 KB |
in6.txt | AC | 3 ms | 896 KB |
in7.txt | AC | 3 ms | 896 KB |
in8.txt | AC | 3 ms | 896 KB |
in9.txt | AC | 3 ms | 896 KB |
sample1.txt | AC | 1 ms | 384 KB |
sample2.txt | AC | 1 ms | 384 KB |
sample3.txt | AC | 1 ms | 384 KB |