Submission #583440

#	Time	Username	Problem	Language	Result	Execution time	Memory
583440		keta_tsimakuridze	LOSTIKS (INOI20_lostiks)	C++14	0 / 100	232 ms	11728 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
const int N = 2e5 + 5, mod = 1e9 + 7; //!
int t, p[N], need[N], rep[N], id[N], d[N], n,  vis[N], par[N],rep2[N], f[N];
int room[N];	
//int n;
vector<int>adj[N];
vector<pair<int, pair<int, pii> > > V[25];
int find(int u) {
	return (par[u] == u ? u : par[u] = find(par[u]));
}
void merge(int u, int v) {
	u = find(u), v = find(v);
	par[u] = v;
}
void dfs(int u, int P) {
	p[u] = P; 
	for(int i = 0; i < V[u].size(); i++) {
		if(V[u][i].f == p[u]) continue;
		rep[V[u][i].f] = V[u][i].s.s.f;
		rep2[V[u][i].f] = V[u][i].s.s.s;
		room[V[u][i].f] = V[u][i].s.f;
		dfs(V[u][i].f, u);
	}
}

int dist(int u,int v) {
	
	queue<int> q;
	for(int i = 1; i <= n; i++) d[i] = n + 5;
	d[u] = 0;
	q.push(u);
	while(q.size()) {
		int u = q.front(); 
		q.pop();
		for(int i = 0; i < adj[u].size(); i++) {
			if(d[adj[u][i]] == n + 5) {
				d[adj[u][i]] = d[u] + 1;
				q.push(adj[u][i]);
			}
		}
	}
	return d[v];
}
main() {
//	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	cin >> n;
	int S, T;
	cin >> S >> T;
	vector< pair<pii, int> > E;
	for(int i = 1; i <= n; i++) par[i] = i;
	set<int> s1;
	for(int i = 2; i <= n; i++) {
		int u, v, t;
		cin >> u >> v >> t;
		adj[u].push_back(v);
		adj[v].push_back(u);
		if(t) {
			E.push_back({{u,v}, t});
			assert(!s1.count(t));
			s1.insert(t);
		}
		else merge(u, v);
	}
	int cur = 0;
	for(int i = 1; i <= n; i++) {
		if(find(i) == i) {
			id[i] = ++cur;
		}
	}
	for(int i = 0; i < E.size(); i++) {
		V[id[find(E[i].f.f)]].push_back({id[find(E[i].f.s)], {E[i].s, {E[i].f.f, E[i].f.s}}});
		V[id[find(E[i].f.s)]].push_back({id[find(E[i].f.f)], {E[i].s, {E[i].f.s, E[i].f.f}}});
	}
	dfs(id[find(S)], 0);
	vis[id[find(S)]] = 1;
	int u = id[find(T)];
	stack<int> s; 
	vector<int> v;
	f[u] = 1;
	while(!vis[u]) {
		s.push(u);
		need[u] = 1;
		u = p[u];
	}
	cur = S;
	int ans = 0, cc = 0;
	while(s.size()) {
		int u = s.top(), x = room[u];
		
		if(vis[u]) continue;
		++cc;
		if(cc > 25) {
			cout << -1;
			return 0;
		}
		if(vis[id[find(x)]]) { 
			ans += dist(cur, x) + dist(x, rep[u]);
			vis[u] = 1;
			if(f[u]) ++ans, cur = rep2[u], --f[u];
			else cur = rep[u];
			need[u] = 0;
			s.pop(); 
			continue;
		}
		vector<int> v;
		x = id[find(x)];
		f[x]++;
		while(!vis[x]) {
			s.push(x);
			x = p[x];
		}
	}
	ans += dist(cur, T);
	cout << ans;
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(long long int, long long int)':
Main.cpp:23:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, std::pair<long long int, long long int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
Main.cpp: In function 'long long int dist(long long int, long long int)':
Main.cpp:41:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for(int i = 0; i < adj[u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main() {
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:77:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int i = 0; i < E.size(); i++) {
      |                 ~~^~~~~~~~~~

• Subtask 1: 0 / 23
• Subtask 2: 0 / 36
• Subtask 3: 0 / 41