Submission #41635

#	Time	Username	Problem	Language	Result	Execution time	Memory
41635		wzy	KOVANICE (COI15_kovanice)	C++11	100 / 100	767 ms	72664 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
int n , m , v;
int dp[300005];
int dp2[300005];
int pai[300005] , peso[300005];
int dg[300005]  , rvdg[300005];
vector<int> adj[300005] ,rvadj[300005];
bool jafoi[300005] , jafoi2[300005];
int fd(int x){
	return pai[x] == x ? x : pai[x] = fd(pai[x]);
}

void join(int i , int j){
	i = fd(i) , j = fd(j);
	if(peso[i] > peso[j]) swap(i,j);
	pai[i] = j , peso[j]++;
}


bool solve(int i , int j , int layer){
	if(jafoi2[i]) return (layer == dp2[i] ? 1 : 0 );
	if(layer == 1){
		dp2[i] = 1;
		return true;
	}
	jafoi2[i] = true;
	bool can = false;
	for(int w = 0 ; w < rvadj[i].size() ; w++){
		int v = rvadj[i][w];
		if(v == j) continue;
		if(jafoi2[v]){
			if(layer -1 == dp2[v]) can = true;
			continue;
		}
		can |= solve(v , i , layer - 1);
	}
	if(can) dp2[i] = layer;
	return can;
}

int32_t main(){
	cin>>n>>m>>v;
	for(int i = 0 ; i < 300005 ; i++){
		pai[i] = i , peso[i] = 0;
	}
	vector< pair<int,int> > ls, bg;
	for(int i = 0 ; i < v ; i++){
		int x , y;
		char p;
		cin>>x>>p>>y;
		if(p == '='){
			join(min(x,y),max(x,y));
		}
		else if(p == '>'){
			bg.pb(pair<int,int>(x,y));
		}
		else{
			ls.pb(pair<int,int>(x,y));
		}
	}
	for(int i = 0 ;i<bg.size();i++){
		bg[i].F = fd(bg[i].F);
		bg[i].S = fd(bg[i].S);
		adj[bg[i].F].pb(bg[i].S);
		dg[bg[i].S]++;
		rvdg[bg[i].F]++;
		rvadj[bg[i].S].pb(bg[i].F);
	}
	for(int i = 0 ;i<ls.size();i++){
		ls[i].F = fd(ls[i].F);
		ls[i].S = fd(ls[i].S);
 		adj[ls[i].S].pb(ls[i].F);
 		dg[ls[i].F]++;
 		rvdg[ls[i].S]++;
 		rvadj[ls[i].F].pb(ls[i].S);
 	}
 	queue<int> q;
 	for(int i = 1  ; i <= m ; i++){
 		if(dg[fd(i)] == 0) q.push(fd(i));
 	}
 	while(!q.empty()){
 		int u = q.front();
 		q.pop();
 		if(jafoi[u]) continue;
 		jafoi[u] = true;
 		for(int j = 0 ; j  <adj[u].size();j++){
 			int v = adj[u][j];
 			dg[v]--;
 			if(dg[v] == 0) q.push(v);
 			dp[v] = max(dp[u] + 1 , dp[v]);
 		}
 	}
 	for(int i = 1 ; i <= m ;i ++){
 		if(dp[fd(i)] == n - 1 && !jafoi2[fd(i)]) q.push(fd(i)) , dp2[fd(i)] = n ;
 	}
 	while(!q.empty()){
 		int u  = q.front();
 		q.pop();
 		if(jafoi2[u]) continue;
 		jafoi2[u] = true;
 		for(int j = 0 ; j < rvadj[u].size() ; j++){
 			int w = rvadj[u][j];
 			if(jafoi2[w]) continue;
 			if(dp[w] + 1 == dp[u]){
 				dp2[w] = dp2[u] - 1;
 				q.push(w);
 			}
 		}
 	}
 	for(int i = 1 ; i <= m ; i++){
 		if(dp2[fd(i)] == 0) puts("?");
 		else{
 			cout<<"K"<<(n - dp2[fd(i)] + 1)<<endl;
 		}
 	} 
}

Compilation message (stderr)

kovanice.cpp: In function 'bool solve(long long int, long long int, long long int)':
kovanice.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int w = 0 ; w < rvadj[i].size() ; w++){
                    ^
kovanice.cpp: In function 'int32_t main()':
kovanice.cpp:67:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ;i<bg.size();i++){
                  ^
kovanice.cpp:75:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ;i<ls.size();i++){
                  ^
kovanice.cpp:92:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j  <adj[u].size();j++){
                       ^
kovanice.cpp:107:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < rvadj[u].size() ; j++){
                      ^

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40