Saratov State University :: Online Contester


::Go
- home
- news
- register
- update personal info
- problemset archive
- submit
- status online
- standing
- contests
- virtual contests
- forum
- statistic
- FAQ
- links
- projects

::Poll
Are you registered on Codeforces?
Yes
No
What is it???

[results]

::webboard

WA on #3
Author: AntiMage@LongquanTemple
ID: 051200
Problem: 101
Contest: 0
Date: 2011-11-28 22:03:03

I have found that the num of lines are larger than the given N,maybe the dfs was wrong.


#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
int x, y, cl, odd_deg, beg, i, n, m, q[10000];
char ron[10000];
struct edge{
int y, rev, id;
bool f;
edge(int xy, int xr, int xi){
y = xy;
rev = xr;
id = xi;
f = true;
}
};
vector<edge> idx[1000];
int dfs(int v){
for(int i=0; i < idx[v].size(); i++){
if(idx[v][i].f==true){
idx[v][i].f = false;
//printf("%d %d %d %d %dn", v, idx[v][i].y, idx[idx[v][i].y][idx[v][i].rev].y, idx[v][i].id, idx[idx[v][i].y][idx[v][i].rev].id);
idx[idx[v][i].y][idx[v][i].rev].f = false;
dfs(idx[v][i].y);
cl++;
q[cl] = abs(idx[v][i].id);
ron[cl] = ((q[cl]==idx[v][i].id)?'+':'-');
}else{
//there is nothing to do!
}
}
return 0;
}
int main(){
freopen("sgu101.in", "r", stdin);
freopen("sgu101.out", "w", stdout);
scanf("%dn", &m);
n = 7;
for(i = 1; i <= m; i++){
scanf("%d %dn", &x, &y);
x++; y++;
idx[x].push_back(edge(y, idx[y].size(), i));
idx[y].push_back(edge(x, idx[x].size()-1, -i));
}
odd_deg = 0;
cl = 0;
beg = 1;
/* for(i = 1; i <= n; i++){
for(int j = 0; j < idx[i].size(); j++){
printf("%d %d %d %dn", idx[i][j].y, idx[i][j].rev, idx[i][j].id, idx[i][j].f);
}
}*/
for(i = 1; i <= n; i++){
if(idx[i].size()>0){beg = i;}
}
for(i = 1; i <= n; i++){
if(idx[i].size()%2==1){odd_deg++; beg = i;}
}
if((odd_deg!=0)&&(odd_deg!=2)){printf("No solutionn");}else{
dfs(beg);
//printf("%d", cl);
if(cl < m){printf("No solutionn");}else{
for(i = cl; i >= 1; i--){printf("%d %cn", q[i], ron[i]);}}
}
fclose(stdin);
fclose(stdout);
return 0;
}

see sub-tree reply to that message


::Login
Forgot password?

::News
22.10.12 - The problems from the Southern Subregional Programming Contest 2012 added to the problemset archive (542 - 553).
22.10.12 - After the start of the contest the statements in PDF will be available by the link.
23.10.11 - The problems from the Southern Subregional Programming Contest 2011 added to the problemset archive (530 - 541).

::Counter

Server time: 2017-11-22 04:49:01Online Contester Team © 2002 - 2016. All rights reserved.