oj.uz

Submission #887992

# Submission time Handle Problem Language Result Execution time Memory
887992 2023-12-15T16:56:47 Z hariaakas646 Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 1000 ms 5564 KB 
#include <bits/stdc++.h>

using namespace std;

#define scd(x) scanf("%d", &x)
#define sclld(x) scanf("%lld", &x)
#define frange(i, n) for(int i=0; i<n; i++)
#define forr(i, l, r) for(int i=l; i<r; i++)
#define all(vec) vec.begin(), vec.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

typedef long long lli;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<lli> vll;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef set<int> seti;

void usaco() {
	freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
}

int n, m;

vector<multiset<int>> graph, gr2;
vb vis;
vi order;

void dfs(int x) {
	vis[x] = true;
	for(auto e : graph[x]) {
		if(!vis[e]) dfs(e);
	}
	order.pb(x);
}

vi comp;
void dfs2(int x) {
	vis[x] = true;
	comp.pb(x);

	for(auto e : gr2[x]) {
		if(!vis[e]) {
			dfs2(e);
		}
	}
}

vi pos;

bool findscc() {
	order = {};
	vis = vb(n+1);

	forr(i, 1, n+1) {
		if(!vis[i]) dfs(i);
	}

	reverse(all(order));
	pos = vi(n+1);
	vis = vb(n+1);
	int id = 1;
	for(auto e : order) {
		if(!vis[e]) {
			comp = {};
			dfs2(e);
			for(auto x : comp) {
				pos[x] = id; 
				// printf("%d ", x);
			}
			// printf("\n");
			id++;
		}
	}

	return pos[1] == pos[n];

}

int main() {
	// usaco();
	scd(n);
	scd(m);
	vector<pair<pii, int>> vec(m);

	gr2 = graph = vector<multiset<int>>(n+1);

	frange(i, m) {
		int u, v, c, d;
		scd(u);
		scd(v);
		scd(c);
		scd(d);
		graph[u].insert(v);
		vec[i] = mp(mp(u, v), d);

		gr2[v].insert(u);
	}

	bool out = findscc();

	lli mi = 1e18;

	if(out) mi = 0;

	for(auto p : vec) {
		// printf("**********\n");
		graph[p.f.f].erase(graph[p.f.f].find(p.f.s));
		gr2[p.f.s].erase(gr2[p.f.s].find(p.f.f));
		graph[p.f.s].insert(p.f.f);
		gr2[p.f.f].insert(p.f.s);
		// forr(i, 1, n+1) {
		// 	for(auto e : graph[i]) printf("%d ", e);
		// 	printf("\n");
		// }
		if(findscc()) {
			mi = min(mi, (lli)p.s);
		}
		gr2[p.f.f].erase(gr2[p.f.f].find(p.f.s));
		graph[p.f.s].erase(graph[p.f.s].find(p.f.f));
		graph[p.f.f].insert(p.f.s);
		gr2[p.f.s].insert(p.f.f);
	}

	if(mi < 1e17) printf("%lld", mi);
	else printf("-1");




}

Compilation message

ho_t4.cpp: In function 'void usaco()':
ho_t4.cpp:25:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(x) scanf("%d", &x)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:87:2: note: in expansion of macro 'scd'
   87 |  scd(n);
      |  ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(x) scanf("%d", &x)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:88:2: note: in expansion of macro 'scd'
   88 |  scd(m);
      |  ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(x) scanf("%d", &x)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:95:3: note: in expansion of macro 'scd'
   95 |   scd(u);
      |   ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(x) scanf("%d", &x)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:96:3: note: in expansion of macro 'scd'
   96 |   scd(v);
      |   ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(x) scanf("%d", &x)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:97:3: note: in expansion of macro 'scd'
   97 |   scd(c);
      |   ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(x) scanf("%d", &x)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:98:3: note: in expansion of macro 'scd'
   98 |   scd(d);
      |   ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Incorrect 16 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1043 ms 5564 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Execution timed out 1088 ms 4384 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Incorrect 16 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -