oj.uz

Submission #41617

# Submission time Handle Problem Language Result Execution time Memory
41617 2018-02-20T02:54:00 Z wzy KOVANICE (COI15_kovanice) C++11
60 / 100
 473 ms 42548 KB 
#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]++;
}

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(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) 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 v =rvadj[u][j];
 			rvdg[v]--;
 			if(rvdg[v] == 0) q.push(v);
 			dp2[v] = dp2[u] - 1;
 		}
 	}
 	for(int i = 1 ; i <= m ; i++){
 		if(dp2[fd(i)] == 0) puts("?");
 		else{
 			cout<<"K"<<(n - dp2[fd(i)] + 1)<<endl;
 		}
 	} 
}

Compilation message

kovanice.cpp: In function 'int32_t main()':
kovanice.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ;i<bg.size();i++){
                  ^
kovanice.cpp:53:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ;i<ls.size();i++){
                  ^
kovanice.cpp:70:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j  <adj[u].size();j++){
                       ^
kovanice.cpp:86:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < rvadj[u].size();j++){
                      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 19192 KB Output is correct
2 Correct 19 ms 19296 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 31332 KB Output is correct
2 Correct 335 ms 32928 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 32928 KB Output is correct
2 Correct 75 ms 32928 KB Output is correct
3 Correct 77 ms 32928 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 473 ms 42548 KB Output isn't correct
2 Halted 0 ms 0 KB -