Submission #955731

#	Time	Username	Problem	Language	Result	Execution time	Memory
955731		n1k	Thousands Islands (IOI22_islands)	C++17	11.90 / 100	50 ms	7756 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){
    	if(cache.count(u))
    		return cache[u];
     
    	par[u] = p;
    	color[u] = min(g[u].size()==1 ? 3 : 1, p==-1?3:color[p]);
     
    	int count = 0;
    	for(auto [v, e]:g[u]){
			if(color[v]==3){
				continue;
			}
    		if(color[v]==1){
    			count++;
    		}else{
    			count += dfs(v, u);
    		}
    	}
     
    	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