Submission #955740

#	Time	Username	Problem	Language	Result	Execution time	Memory
955740		n1k	Thousands Islands (IOI22_islands)	C++17	11.90 / 100	47 ms	7544 KiB

islands

    #include "islands.h"
     
    #include <bits/stdc++.h>
     
    using namespace std;
     
    vector<vector<array<int, 2>>> g;
    vector<int> color, par;
     
    map<int, int> cache;
     
    int x, y;
     
    int dfs(int u, int p, bool point_of_interest=0){
    	if(cache.count(u))
    		return cache[u];
     
    	par[u] = p;
		if(point_of_interest){
			color[u] = 1;
		}else{
			color[u] = g[u].size() == 1 ? 3 : 1;
		}
		if(color[u]!=3){
			point_of_interest = 1;
		}
     
    	int count = 0;
    	for(auto [v, e]:g[u]){
			if(color[v]==3){
				continue;
			}
    		if(color[v]==1){
    			count++;
    		}else{
    			count += min(1, dfs(v, u, point_of_interest));
    		}
    	}
     
    	color[u] = max(2, color[u]);
     
    	return cache[u] = min(2, count);
    }
     
    std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
    	g.assign(N, {});
    	color.assign(N, {});
    	par.assign(N, {});
     
    	for(int i=0; i<M; i++){
    		g[U[i]].push_back({V[i], i});
    	}
     
    	return dfs(0, -1) >= 2;
    }

• Subtask 1: 1.75 / 5
• Subtask 2: 1.75 / 5
• Subtask 3: 0 / 21
• Subtask 4: 8.399999999999999 / 24
• Subtask 5: 0 / 45