| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 41635 |
2018-02-20T04:07:44 Z |
wzy |
KOVANICE (COI15_kovanice) |
C++11 |
|
767 ms |
72664 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]++;
}
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
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++){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
19192 KB |
Output is correct |
| 2 |
Correct |
20 ms |
19440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
351 ms |
32684 KB |
Output is correct |
| 2 |
Correct |
350 ms |
34084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
34084 KB |
Output is correct |
| 2 |
Correct |
82 ms |
34084 KB |
Output is correct |
| 3 |
Correct |
86 ms |
34084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
720 ms |
51300 KB |
Output is correct |
| 2 |
Correct |
634 ms |
54912 KB |
Output is correct |
| 3 |
Correct |
537 ms |
58696 KB |
Output is correct |
| 4 |
Correct |
622 ms |
68244 KB |
Output is correct |
| 5 |
Correct |
767 ms |
72664 KB |
Output is correct |
