oj.uz

답안 #203023

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
203023 2020-02-19T03:43:23 Z galen_colin 꿈 (IOI13_dreaming) C++14
18 / 100
 1000 ms 18552 KB 
#include <bits/stdc++.h>
#include <chrono> 
 
using namespace std;
using namespace std::chrono; 
 
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
// #pragma optimization_level 3
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define f0r(a, b) for (long long a = 0; a < (b); a++)
#define f1r(a, b, c) for (long long a = (b); a < (c); a++)
#define f0rd(a, b) for (long long a = (b); a >= 0; a--)
#define f1rd(a, b, c) for (long long a = (b); a >= (c); a--)
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define pb push_back
#define io {ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define mp make_pair
#define f first
#define s second
#define presum(p, a, n) {p[0] = a[0]; for (int i = 1; i < (n); i++) p[i] = a[i] + p[i-1];}
#define all(v) v.begin(), v.end()
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define readgraph(list, edges) for (int i = 0; i < edges; i++) {int a, b; cin >> a >> b; a--; b--; list[a].pb(b); list[b].pb(a);}
#define ai(a, n) for (int ele = 0; ele < n; ele++) cin >> a[ele];
#define ain(a, lb, rb) for (int ele = lb; ele <= rb; ele++) cin >> a[ele];
#define ao(a, n) {for (int ele = 0; ele < n; ele++) { if (ele) cout << " "; cout << a[ele]; } cout << '\n';}
#define aout(a, lb, rb) {for (int ele = lb; ele <= rb; ele++) { if (ele > lb) cout << " "; cout << a[ele]; } cout << '\n';}
typedef long long ll;
typedef double ld;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
 
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
  cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
  cin >> p.first;
  return cin >> p.second;
}
 
// template<typename A, typename B> ll max(A x, B y) {
//   return x > y ? x : y;
// }
// template<typename A, typename B> ll min(A x, B y) {
//   return x < y ? x : y;
// }
 
mt19937 rng(steady_clock::now().time_since_epoch().count());
/* usage - just do rng() */
 
void usaco(string filename) {
  // #pragma message("be careful, freopen may be wrong")
	freopen((filename + ".in").c_str(), "r", stdin);
	freopen((filename + ".out").c_str(), "w", stdout);
}
 
const lld pi = 3.14159265358979323846;
const ll mod = 1000000007;
// const ll mod = 998244353;

// int travelTime(int n, int m, int l, int a[], int b[], int t[]);

// int main() {
//   int n = 3;
//   int m = 2;
//   int l = 5;
//   int a[2] = {0, 1};
//   int b[2] = {1, 2};
//   int t[2] = {3, 3};
//   int x = travelTime(n, m, l, a, b, t);
//   cout << x << endl;
// }

#include "dreaming.h"
 
ll n, m, k, q, Q, T, l, r, x, y, z;
ll a[1000005];
ll b[1000005];
ll c[1000005];
string s, t;
ll ans = 0;

vl tdists;
vpi edges[300005];
bool vis[300005];
int mk[300005];
int ngroup = 0;
ll mx[300005];

void mark(int x) {
  if (vis[x]) return;
  vis[x] = 1;
  mk[x] = ngroup;

  for (pii y: edges[x]) mark(y.f);
}

ll gdist(int x, ll d) {
  if (vis[x]) return 0;
  vis[x] = 1;

  ll mv = d;
  for (pii y: edges[x]) mv = max(mv, gdist(y.f, d + y.s));
  return mv;
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
  f0r(i, m) {
    edges[a[i]].pb(mp(b[i], t[i]));
    edges[b[i]].pb(mp(a[i], t[i]));
  }
  
  f0r(i, n) mk[i] = -1;
  ms(vis, 0);
  f0r(i, n) {
    if (!vis[i]) {
      mark(i);
      ++ngroup;
    }
  }

  ll ans = 0;
  ms(mx, 0);
  f0r(i, n) {
    ms(vis, 0);
    ll v = gdist(i, 0);
    ans = max(ans, v);
    mx[mk[i]] = max(mx[mk[i]], v);
  }

  f0r(i, ngroup) tdists.pb(mx[i]);
  sort(all(tdists));
  reverse(all(tdists));
  if (tdists.size() == 2) ans = max(ans, tdists[0] + tdists[1] + l);
  else if (tdists.size() > 2) {
    ans = max(ans, tdists[0] + tdists[1] + l);
    ans = max(ans, tdists[1] + tdists[2] + 2 * l);
  }

  return ans;
}

// int main() {
//   io;
//   // freopen("case", "r", stdin);
//   // freopen("test.txt", "r", stdin);
//   // freopen("case", "w", stdout);
//   // freopen("file.in", "r", stdin);
 
//   // usaco("file");
 
  
// }

Compilation message

dreaming.cpp: In function 'void usaco(std::__cxx11::string)':
dreaming.cpp:65:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((filename + ".in").c_str(), "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:66:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((filename + ".out").c_str(), "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1101 ms 18552 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1101 ms 18552 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1101 ms 18552 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 928 ms 13408 KB Output is correct
2 Correct 883 ms 13560 KB Output is correct
3 Correct 898 ms 13400 KB Output is correct
4 Correct 887 ms 13432 KB Output is correct
5 Correct 862 ms 13304 KB Output is correct
6 Correct 932 ms 14068 KB Output is correct
7 Correct 897 ms 13432 KB Output is correct
8 Correct 824 ms 13352 KB Output is correct
9 Correct 814 ms 13300 KB Output is correct
10 Correct 869 ms 13428 KB Output is correct
11 Correct 14 ms 9976 KB Output is correct
12 Correct 887 ms 11740 KB Output is correct
13 Correct 854 ms 11760 KB Output is correct
14 Correct 901 ms 11760 KB Output is correct
15 Correct 886 ms 11760 KB Output is correct
16 Correct 873 ms 11624 KB Output is correct
17 Correct 897 ms 11632 KB Output is correct
18 Correct 856 ms 11632 KB Output is correct
19 Correct 888 ms 11632 KB Output is correct
20 Correct 11 ms 9976 KB Output is correct
21 Correct 10 ms 9976 KB Output is correct
22 Correct 37 ms 10104 KB Output is correct
23 Correct 900 ms 11632 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1101 ms 18552 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1101 ms 18552 KB Time limit exceeded
2 Halted 0 ms 0 KB -